链接：https://ac.nowcoder.com/acm/contest/893/H
来源：牛客网
在Casya生活的世界里，一天由m个小时组成。
最近Casya的女神终于答应在接下来的n天中与Casya聊天,Casya非常激动。
在这n天中的每一天的每一个小时中女神可能会在线或者不在线，
某个小时如果女神如果在线且Casya在线的话他们就会开心的聊一个小时；
反之如果女神在线Casya没有在线的话女神就会认为Casya放了她的鸽子而积累一点生气度。
而Casya是个很懒惰的人，他每天只愿意上线一次，当他某天下线后就不愿意再上线了。
换句话说，他每天在线的时间必须是连续的。
现在Casya已经知道每一天的每个小时女神是否会在线
Casya希望在这n天中女神的总生气度不超过k，在此前提下Casya希望他的总上线时间最小。
假设每个小时Casya和女神要么完整在线要么完整不在线，请问Casya在这n天中最小的总上线时间是多少小时？

一道简单的dp题。
对题目进行分析，要求的是使女神总生气度不超过k的最小总上线时间，换句话说那就是（咕了女神k小时使得我们获得的最大不在线时间）。想到这点接下来就可以写了。

首先我们对每天女神在线时间的做个预处理，统计下前缀和和个数。

    scanf("%s",a+1);
    for(int j=1;j<=m;j++){
        if(a[j]=='0')f[j]=f[j-1];
        else f[j]=f[j-1]+1,cnt[i]++;
    }

然后假使咕了女神所有的在线时间，那我们得到的价值当然就是一整天了，也就是

    s[i][cnt[i]]=m;

然后，因为数据比较小，我们再直接跑个m方的暴力就可以求出在第i天咕女神x（x<cnt[i]）次所带来的最大休息时间。

for(int p=1;p<=m;p++){
     for(int q=p;q<=m;q++){
         s[i][cnt[i]-f[q]+f[p-1]]=max(s[i][cnt[i]-f[q]+f[p-1]],m-(q-p+1));
         /* (p,q)为我假设的在线时间，通过前缀和计算得出(p,q)之间的女神在线时长:f[q]-f[p-1]. 所以咕了女神的时间x即是 cnt[i]-(f[q]-f[p-1]) 然后我们因此获得的休息时间t是 m-(p-q+1) 所以在这一天咕女神x小时获得的休息时间可以更新为 min(s[i][x],t) 也就是 s[i][x]=min(s[i][x],t) */
     }
 }

算完所有天的情况后，就是一个背包了：已知每天咕女神 0到cnt[i] 小时所带来的价值，最多可以咕k个小时，请问我怎么取能使得到的价值最大？
因为每天只能选择一种情况，所以是分组背包，开个二维数组记录一下
显然可得我们取k个小时肯定是最优的，因为对于任意k-1的情况，我们可以在他的基础上再咕掉任意一个还没咕的小时，再向前推也是同理。

for(int i=1;i<=n;i++){//第i天
    for(int j=0;j<=cnt[i];j++){//咕女神j个小时
        for(int l=k;l>=j;l--){//从后往前更新
            ans[i][l]=max(ans[i][l],ans[i-1][l-j]+s[i][j]);
        }
    }
}

所以我们就求得了答案ans[n][k]
然后我们要求的是花的最小时间，也就是总时间减去最大休息时间，输出即可。

完整代码：

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define FI first
#define SE second
#define PB push_back
#define POP pop_back
#define D double
#define endl '\n'
typedef pair<int,int> PII;
const LL INF=1e18,mod=100000000;
const int N=2e5+7;
int n,m,k;
char a[222];
int s[222][222];//第一维表示天数，第二维表示改天咕女神的小时数，也就是在第i天咕女神j小时获得的最大不在线时间
int f[222];//统计每天女神在线时长的前缀和用的滚动数组
int cnt[222];//女神每天的在线时长
int ans[222][222];//二维背包容器
int main()
{
    int t;
    cin>>t;
    while(t--){
        memset(s,0,sizeof(s));
        memset(cnt,0,sizeof(cnt));
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=n;i++){
            scanf("%s",a+1);
            for(int j=1;j<=m;j++){
                if(a[j]=='0')f[j]=f[j-1];
                else f[j]=f[j-1]+1,cnt[i]++;
            }
            s[i][cnt[i]]=m;
            for(int p=1;p<=m;p++){
                for(int q=p;q<=m;q++){
                    s[i][cnt[i]-f[q]+f[p-1]]=max(s[i][cnt[i]-f[q]+f[p-1]],m-(q-p+1));
                }
            }
        }
        int num=m*n;
        memset(ans,0,sizeof(ans));
        for(int i=1;i<=n;i++){
            for(int j=0;j<=cnt[i];j++){
                for(int l=k;l>=j;l--){
                    ans[i][l]=max(ans[i][l],ans[i-1][l-j]+s[i][j]);
                }
            }
        }
        printf("%d\n",num-ans[n][k]);
    }
    return 0;
}