1 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N=55,M=55,T=2505; int f[M][M],dp[N][T],sum[M]; char s[N]; int main() { int n,m,t; cin>>n>>m>>t; for(int i=1;i<=n;i++) { scanf("%s",s+1); for(int j=1;j<=m;j++) sum[j]=sum[j-1]+(s[j]=='1'); for(int j=1;j<=m;j++)//前j个格子 //上下两行顺序可换 for(int k=1;k<=j;k++)//刷k次 最多正确的格子数 { f[j][k]=0; for(int p=k-1;p<j;p++)//最后一次刷的前面断点 { int tmp=sum[j]-sum[p]; f[j][k]=max(f[j][k],f[p][k-1]+max(tmp,j-p-tmp)); } } for(int k=1;k<=t;k++)//前i行刷k次 { int tmp=min(m,k); for(int j=0;j<=tmp;j++)//留给最后一行刷的次数 dp[i][k]=max(dp[i][k],dp[i-1][k-j]+f[m][j]); } } int ans=0; for(int i=1;i<=t;i++) ans=max(ans,dp[n][i]); cout<<ans<<endl; return 0; }
- 1
信息
- ID
- 697
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 25
- 已通过
- 4
- 上传者