2018.12.08 codeforces 946D. Timetable（背包）

傳送門
題意簡述：有一個人上n天課，每天有m個小時的時間安排表（一個01串），為1表示要上課，否則不上課，求出如果可以最多翹$k$節課這$n$天在校待的總時間的最小值（一天必須在所有課上完后才能離開）。

---

背包$sb$題。
注意可以從首尾分別逃課。
對于每天的上課情況我們都預處理出一個數組aia_iai?表示這天逃$i$節課在校的最少時間。
然后跑分組背包就可以了。
實際上可以滾動數組優化一波。
代碼：

#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=505;
int n,m,K,a[N],f[2][N],pos[N],tmp=0;
char s[505];
inline void solve(int*pos,int tot,int*a){if(!tot){for(ri i=0;i<=K;++i)a[i]=0;return;}int up=min(K,tot);for(ri tim=0;tim<=up;++tim){if(tim==tot){a[tim]=0;break;}a[tim]=0x3f3f3f3f;for(ri lt=0,rt=tim;lt<=tim;++lt,--rt)a[tim]=min(a[tim],pos[tot-rt]-pos[lt+1]+1);}for(ri i=up+1;i<=K;++i)a[i]=a[i-1];
}
int main(){freopen("lx.in","r",stdin);scanf("%d%d%d",&n,&m,&K);for(ri i=1,cnt=0,tot=0;i<=n;++i,cnt=tot=0){scanf("%s",s+1),tmp^=1,memset(f[tmp],0x3f,sizeof(f[tmp]));for(ri j=1;j<=m;++j)if(s[j]=='1')pos[++tot]=j;solve(pos,tot,a);for(ri j=0;j<=K;++j)for(ri k=0;k<=j;++k)f[tmp][j]=min(f[tmp][j],f[tmp^1][k]+a[j-k]);}cout<<f[tmp][K];return 0;
}