萌新求助简单dp 30pts
查看原帖
萌新求助简单dp 30pts
390770
D2T1xubiaoshi楼主2022/6/29 14:19
//P4158
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

const int N = 55;
int n, m, t, sum[N], w[N][N], f[N][N*N];
char s[N]; 

int cost(int l, int r){
	int k = sum[r] - sum[l-1], len = r - l + 1;
	return max(k, len - k);
}

int main(){
	scanf("%d%d%d", &n, &m, &t);
	for(int i = 1; i <= n; ++ i){
		scanf("%s", s + 1);
		memset(sum, 0, sizeof(sum));
		for(int j = 1; j <= m; ++ j){
			if(s[j] == '1') ++ sum[j];
			sum[j] += sum[j-1];
		}
		//w[j,k] 第i行前j个改k次
		//f[i,j] 前i行改j次 
		for(int j = 1; j <= m; ++ j){
			for(int k = 1; k <= m; ++ k){
				for(int l = 0; l < j; ++ l){
					w[j][k] = max(w[j][k], w[l][k-1] + cost(l+1, j));
				}
			}
		}
		for(int j = 1; j <= m; ++ j){
			for(int k = 0; k <= j; ++ k){
				f[i][j] = max(f[i][j], f[i-1][k] + w[m][j-k]);
//				printf("%d %d %d\n", i, j, f[i][j]);
			}
		}
		memset(w, 0, sizeof(w));
	}
	printf("%d\n", f[n][t]);
	return 0;
}

qwq

2022/6/29 14:19
加载中...