Educational Codeforces Round 39 (Rated for Div. 2) D. Timetable - dp分组背包

题目链接：https://codeforces.com/problemset/problem/946/D
题目大意：有n周，每周有m个小时。每节课1个小时。1代表有课。0代表没有课。现在可以逃k节课。每一天他都会从第一节课开始。到最后一课结束。问他现在可以逃k次课。让他在学校的时间最少。最小值为多少？

思路：对于第i周。我们可以用v[i][j]表示：第i周逃j节课在学校的最小时间。因为要结果最小。那么这些要上的课肯定是连续的。直接O（n^2）预处理。

每一周为一组。进行分组背包。
f[i][j]：为前i周逃j次课的在学校最小时间。枚举第i周逃k几课进行转移。

#include<bits/stdc++.h>
#define LL long long
using namespace std;

vector<int> a[505];
int v[505][505];//在i周逃j天
int f[2][505];
int main(){

    int n, m, K, x, s1=0;
    scanf("%d%d%d", &n, &m, &K);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            scanf("%1d", &x);
            if(x==1){
                a[i].push_back(j);
                s1++;
            }
        }
    }

    if(s1<=K){
        printf("0\n");
        return 0;
    }

    memset(v, 7, sizeof(v));
    for(int i=1; i<=n; i++){

        v[i][a[i].size()]=0;

        for(int j=0; j<a[i].size(); j++){
            for(int k=j; k<a[i].size(); k++){
                v[i][a[i].size()-(k-j+1)]=min(v[i][a[i].size()-(k-j+1)], a[i][k]-a[i][j]+1);
            }
        }
    }

    memset(f, 7, sizeof(f));
    f[0][0]=0;

    int I=0;//滚动数组优化
    for(int i=1; i<=n; i++){
        I^=1;
        memset(f[I], 7, sizeof(f[I]));//记得初始化
        for(int j=K; j>=0; j--){
            for(int k=0; k<=j; k++){
                f[I][j]=min(f[I][j], f[I^1][j-k]+v[i][k]);
            }
        }
    }
    printf("%d\n", f[I][K]);

    return 0;
}