Chat（分组背包）

链接：https://ac.nowcoder.com/acm/contest/893/H
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

在Casya生活的世界里，一天由m个小时组成。
最近Casya的女神终于答应在接下来的n天中与Casya聊天,Casya非常激动。

在这n天中的每一天的每一个小时中女神可能会在线或者不在线，
某个小时如果女神如果在线且Casya在线的话他们就会开心的聊一个小时；
反之如果女神在线Casya没有在线的话女神就会认为Casya放了她的鸽子而积累一点生气度。

而Casya是个很懒惰的人，他每天只愿意上线一次，当他某天下线后就不愿意再上线了。
换句话说，他每天在线的时间必须是连续的。

现在Casya已经知道每一天的每个小时女神是否会在线

Casya希望在这n天中女神的总生气度不超过k，在此前提下Casya希望他的总上线时间最小。
假设每个小时Casya和女神要么完整在线要么完整不在线，请问Casya在这n天中最小的总上线时间是多少小时？

输入描述:

第一行一个数字T(1≤T≤30)T(1≤T≤30)--样例个数。

每个样例第一行三个数字n,m,k(1≤n,m≤200,0≤k≤200)n,m,k(1≤n,m≤200,0≤k≤200)。
然后这n行，每行一个长度为m的只含'0'和'1'的字符串，
第i个字符串的第j个字符为'0'代表女神第i天的第j个小时不在线，为'1'表示女神第i天的第j个小时在线。

保证所有样例中∑n×m∑n×m不超过5×1055×105。

输出描述:

每个样例输出一行一个数字--Casya在这n天中最小的总上线时间

示例1

输入

复制

输出

复制

5
8

说明

第一个样例:
一种可行的方案:
Casya第一天只在第2个小时上线，第五个小时女生在线而Casya不在线，生气度积累1；
Casya第一天在第1、2、3、4个小时上线。
Casya的总上线时间是1+4=5。
第二个样例:
只能老老实实上线。
Casya第一天在第2、3、4、5个小时上线；
Casya第一天在第1、2、3、4个小时上线。
Casya的总上线时间是4+4=8。

让女神不生气所用的总的时间 - 让女神生气k所能省的最大时间就是答案

写错了一个变量，找了好久才找出来，(╥╯^╰╥)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<list>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
const int N=205;
int p[N],a[N];
int dp[N][N],d[N][N];//d[i][j]代表第i天生气j能省的最多时间 ,dp[i][j]代表到第i天生气j能省的最多时间 
int n,m,k,sum=0;
void solve(string s,int k) {//第k天预处理
	int pos=0;
	for(int i=0; i<m; i++) {
		if(s[i]=='1') p[++pos]=i;
	}
	a[k]=pos;
	for(int i=0;i<=pos;i++){
		d[k][i]=0;
	}
	int st;
    if(pos==0) st=0;
    else st=p[pos]-p[1]+1;
	for(int i=1;i<=pos;i++){
		for(int j=i;j<=pos;j++){
			int q=pos-(j-i+1);//造成生气值 
			int t=p[j]-p[i]+1;//在线的时间 
			d[k][q]=max(d[k][q],st-t);
		}
	}
	d[k][pos]=st;
	sum+=st; 
}
int main() {
	ios::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--) {
		cin>>n>>m>>k;
		string s;
		sum=0;
		for(int i=1; i<=n; i++) {
			cin>>s;
			solve(s,i);
		}
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++){
			for(int j=k;j>=0;j--){
				dp[i][j]=dp[i-1][j];
				for(int c=0;c<=a[i];c++){
					if(j>=c) dp[i][j]=max(dp[i][j],dp[i-1][j-c]+d[i][c]);
					else break;
				}
			}
		}
		int ans=sum-dp[n][k];
		cout<<ans<<endl;
	}
	return 0;
}