Timetable
题意：ivan 是一个学生， 他们当地一周有n天， 每天有m节课，每节课一小时， 然后‘1’代表的是ivan这个时间段需要上课， 现在ivan可以跳过选择K节课不去上， 他在学校的时间为当天他选择的第一节课到当天的最后一节课，也就是可以跳2端的课， 如果当天的没有课， 当天就不需要去学校。现在求这周ivan去学校的时间最小是多少。
题解：算出不逃课的情况下的总时间， 然后用分组背包（因为每天只能有一种情况， 所以只能在每组里面选一种），跑出逃课k节下最多的逃课时间是多少， 总时间-逃课时间就是答案了。
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 #define ULL unsigned LL 5 #define fi first 6 #define se second 7 #define lson l,m,rt<<1 8 #define rson m+1,r,rt<<1|1 9 #define max3(a,b,c) max(a,max(b,c))10 const int INF = 0x3f3f3f3f;11 const LL mod = 1e9+7;12 typedef pair<int,int> pll;13 const int N = 5e3+10;14 char str[N];15 int dp[N];16 int pos[N];17 int len[N];18 int n, m, k;19 int main(){20 ????scanf("%d%d%d", &n, &m, &k);21 ????int tot = 0;22 ????for(int i = 1; i <= n; i++) {23 ????????scanf("%s", str+1);24 ????????int cnt = 0;25 ????????for(int j = 1; j <= m; j++)26 ????????????if(str[j] == ‘1‘)27 ????????????????pos[++cnt] = j;28 ????????if(cnt == 0) continue;29 ????????memset(len, 0, sizeof(len));30 ????????int llen = pos[cnt]-pos[1]+1;31 ????????tot += llen;32 ????????for(int to = 1; to <= k && to <= cnt; to++){33 ????????????????for(int r = cnt - to, l = 1; r >= l && r <= cnt; r++, l++)34 ????????????????????len[to] = max(len[to], llen - (pos[r] - pos[l] + 1));35 ????????????????if(to == cnt)36 ????????????????????len[to] = llen;37 ????????????}38 ????????for(int j = k; j >= 1; j--)39 ????????????for(int to = 1; to <= j && to <= cnt; to++)40 ????????????????dp[j] = max(dp[j], dp[j-to]+len[to]);41 ????}42 ????printf("%d", tot - dp[k]);43 ????return 0;44 }CodeForces 946D Timetable
原文地址：https://www.cnblogs.com/MingSD/p/8534301.html