题目链接：http://codeforces.com/problemset/problem/946/D
题目大意：有n个字符串，代表n天的课表，1表示这个时间要上课，0表示不要上课，一天在学校时间为第一节课到最后一节课的时间。总共，可以逃过k次课，求至少需要在学校多少时间。
解题思路：听了大佬说背包，然后预处理就想了20多分钟，比赛结束，GG。。。先是预处理出v[i][k]即第i天逃k节课的能节约的最多时间，至于怎么求，直接枚举k,然后枚举两端1的位置即可。然后就可以做分组背包了，这就不说了，很简单。
代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 typedef long long LL; 7 const int N=1e3+5; 8 const int INF=0x3f3f3f3f; 9 10 char s[N][N];11 int num[N],pos[N][N],dp[N],v[N][N]; ????????//pos[i][j]对应第i个字符串第j个‘1‘的位置，num[i]记录第i个字符串‘1‘的数量12 ????????????????????????????????????????????//v[i][k]即第i段字符串删除k个1节约的时间13 int main(){14 ????int n,m,lim;15 ????scanf("%d%d%d",&n,&m,&lim);16 ????for(int i=0;i<n;i++){17 ????????scanf("%s",s[i]);18 ????????for(int j=0;j<m;j++){19 ????????????if(s[i][j]==‘1‘){20 ????????????????num[i]++;21 ????????????????pos[i][num[i]]=j;22 ????????????}23 ????????}24 ????}25 ????//处理出v[i][k],26 ????for(int i=0;i<n;i++){27 ????????int cnt=0;28 ????????//枚举k29 ????????for(int k=0;k<=min(num[i]-1,lim);k++){30 ????????????int res=INF;31 ????????????//左进p个1,右进q个132 ????????????for(int p=0;p<=k;p++){33 ????????????????int q=(k-p);34 ????????????????res=min(res,pos[i][num[i]-q]-pos[i][p+1]+1);35 ????????????}36 ????????????v[i][k]=m-res;37 ????????}38 ????????v[i][num[i]]=m;39 ????}40 ????//分组背包41 ????memset(dp,0,sizeof(dp));42 ????for(int i=0;i<n;i++){43 ????????for(int j=lim;j>=0;j--){44 ????????????for(int k=0;k<=min(j,m);k++){45 ????????????????dp[j]=max(dp[j],dp[j-k]+v[i][k]);46 ????????????}47 ????????}48 ????}49 ????printf("%d\n",m*n-dp[lim]);50 ????return 0;51 }Codeforces 946D Timetable（预处理+分组背包）
原文地址：https://www.cnblogs.com/fu3638/p/8520285.html