仿站容易还是建站容易,有什么较好的网站开发框架,网页制作素材包,企业家居网站建设传送门 题意简述#xff1a;有一个人上n天课#xff0c;每天有m个小时的时间安排表#xff08;一个01串#xff09;#xff0c;为1表示要上课#xff0c;否则不上课#xff0c;求出如果可以最多翘kkk节课这nnn天在校待的总时间的最小值#xff08;一天必须在所有课上完… 传送门 题意简述有一个人上n天课每天有m个小时的时间安排表一个01串为1表示要上课否则不上课求出如果可以最多翘kkk节课这nnn天在校待的总时间的最小值一天必须在所有课上完后才能离开。 背包sbsbsb题。 注意可以从首尾分别逃课。 对于每天的上课情况我们都预处理出一个数组aia_iai表示这天逃iii节课在校的最少时间。 然后跑分组背包就可以了。 实际上可以滚动数组优化一波。 代码 #includebits/stdc.h
#define ri register int
using namespace std;
const int N505;
int n,m,K,a[N],f[2][N],pos[N],tmp0;
char s[505];
inline void solve(int*pos,int tot,int*a){if(!tot){for(ri i0;iK;i)a[i]0;return;}int upmin(K,tot);for(ri tim0;timup;tim){if(timtot){a[tim]0;break;}a[tim]0x3f3f3f3f;for(ri lt0,rttim;lttim;lt,--rt)a[tim]min(a[tim],pos[tot-rt]-pos[lt1]1);}for(ri iup1;iK;i)a[i]a[i-1];
}
int main(){freopen(lx.in,r,stdin);scanf(%d%d%d,n,m,K);for(ri i1,cnt0,tot0;in;i,cnttot0){scanf(%s,s1),tmp^1,memset(f[tmp],0x3f,sizeof(f[tmp]));for(ri j1;jm;j)if(s[j]1)pos[tot]j;solve(pos,tot,a);for(ri j0;jK;j)for(ri k0;kj;k)f[tmp][j]min(f[tmp][j],f[tmp^1][k]a[j-k]);}coutf[tmp][K];return 0;
}转载于:https://www.cnblogs.com/ldxcaicai/p/10367840.html
