C++(clang++ 11.0.1) 解法, 执行用时: 268ms, 内存消耗: 25096K, 提交时间: 2023-04-02 16:57:47

#include<bits/stdc++.h>
using namespace std;
// #define int long long
typedef pair<int,int> PII;
const int N =2510,mod=1e9+7,inf=0x3f3f3f3f;
int a[N],s[N];
int f[N][N];
int get(int l,int r)
{
	return max(s[r]-s[l-1],r-l+1-(s[r]-s[l-1]));
}
int main()
{
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1;i<=n*m;i++)scanf("%1d",&a[i]),s[i]=s[i-1]+a[i];
	memset(f,-0x3f,sizeof f);
	f[0][0]=0;
	for(int i=1;i<=n*m;i++)
		for(int j=1;j<=k;j++)
		{
			int len=i%m;
			if(len==0)len=m;
			f[i][j]=f[i-1][j];
			for(int l=1;l<=len;l++)
			{
				f[i][j]=max(f[i][j],f[i-l][j-1]+get(i-l+1,i));
			}
		}
	cout<<f[n*m][k];
}

pypy3 解法, 执行用时: 129ms, 内存消耗: 39332K, 提交时间: 2021-06-03 13:59:10

n, m, t = map(int, input().split())
s = [input().strip() for _ in range(n)]
dp = [[0] * (t + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
	c, p = [], None
	for x in s[i - 1]:
		if not c or p != x: c.append(1); p = x
		else: c[-1] += 1
	z, f = [0], [0] * (len(c) + 1)
	for _ in range(len(c)):
		for j in range(len(c), 0, -1):
			v = [0, 0]
			for k in range(j - 1, -1, -1):
				v[k % 2] += c[k]
				f[j] = max(f[j], f[k] + max(v))
		z.append(f[-1])
	for j in range(t + 1):
		for k in range(len(z)):
			if j + k > t: break
			dp[i][j + k] = max(dp[i][j + k], dp[i - 1][j] + z[k])
print(dp[n][t])

C++14(g++5.4) 解法, 执行用时: 47ms, 内存消耗: 51428K, 提交时间: 2020-05-01 11:03:27

#include<cstdio>
#define N 51
int max(int a,int b){return a>b?a:b;}
int f[N][N][N*N][2],s,n,m,t;
char a[N][N];
int main()
{
    scanf("%d%d%d",&n,&m,&t);
    for (int i=1;i<=n;i++) scanf("%s",a[i]+1);
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) for (int k=1;k<=t;k++) for (int l=0;l<2;l++)
    {
        if (j==1) f[i][j][k][l]=max(f[i-1][m][k-1][0],f[i-1][m][k-1][1])+(a[i][j]==l+'0');
        else f[i][j][k][l]=max(f[i][j-1][k][l],f[i][j-1][k-1][l^1])+(a[i][j]==l+'0');
    }
    printf("%d",max(f[n][m][t][0],f[n][m][t][1]));
    return 0;
}