1 条题解

  • 0
    @ 2026-4-18 10:44:46
    #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
    上传者