Chat

第一行一个数字 $T(1 \le T \le 30)$ --样例个数。

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

保证所有样例中 $\sum n \times m$ 不超过 $5 \times 10^{5}$ 。

C++11(clang++ 3.9) 解法, 执行用时: 146ms, 内存消耗: 1108K, 提交时间: 2019-05-07 23:56:17

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

const int N = 205;
#define REP(i,s,t) for(int i=s;i<=t;i++)
int dp[N],val[N][N],sum[N];
char s[N];
int n,m,k;

inline void init(){
	memset(val,0,sizeof(val));
	REP(i,1,n){
		memset(sum,0,sizeof(sum));
		scanf("%s",s+1);
		for(int j=1;j<=m;j++){
			sum[j]=sum[j-1]+s[j]-'0';
		}
		val[i][sum[m]]=m;
		REP(j,1,m) REP(g,1,j){    
			int len=j-g+1;
			int num=sum[m]-(sum[j]-sum[g-1]);      
			val[i][num]=max(val[i][num],m-len);
		}
	}
}
int main(){
	int T;cin>>T;
	while(T--){
		cin>>n>>m>>k;
		init();
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++){
			for(int j=k;j>=0;j--){
				for(int g=0;g<=m;g++){    
					if(j>=g)dp[j]=max(dp[j],dp[j-g]+val[i][g]);
				}
			}
		}
		printf("%d\n",n*m-dp[k]);
	}
}

C++14(g++5.4) 解法, 执行用时: 161ms, 内存消耗: 860K, 提交时间: 2019-05-07 16:31:09

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int dp[205],sum[205],mx[205];
char s[205][205];
int main(){
	int t;scanf("%d",&t);
	while(t--){
		memset(dp,0,sizeof(dp));
		int n,m,k;scanf("%d%d%d",&n,&m,&k);
		for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
		for(int i=1;i<=n;i++){
			memset(mx,0,sizeof(mx));
			for(int j=1;j<=m;j++)
			sum[j]=s[i][j]-'0'+sum[j-1];
			mx[sum[m]]=m;
			for(int j=1;j<=m;j++){
				for(int w=j;w<=m;w++){
					int tot=sum[m]-(sum[w]-sum[j-1]);
					mx[tot]=max(mx[tot],m-w+j-1);
				}
			}
			for(int j=k;j>=0;j--){
				for(int w=0;w<=m;w++){
					if(j-w>=0)dp[j]=max(dp[j],dp[j-w]+mx[w]);
				}
			}
		}
		printf("%d\n",m*n-dp[k]);
	}
	return 0;
}

详情