这题一看不会 在看了半天像dp 想半天推不出转移方程 不知道怎么写
经过对大佬们的博客的学习 终于弄懂了一种解决方法(大佬怎么写都是对的 渣渣怎么写都是错的QAQ
三个数组:dp[i][j][k] 第i个木板k个格子粉刷j次 正确格子数
sum[i][j] 第i个木板j个格子1的数量
ins[i][j] 前i个木板粉刷j次 正确格子数
详细解析看代码(代码里解释的很清楚
#include <bits/stdc++.h>
#define ll long long
ll const N=55;
ll const M=2505;
using namespace std;
int n,m,t;
ll dp[N][M][N],sum[N][N],ins[N][M];
string s;
int main()
{
cin>>n>>m>>t;
for(int i=1;i<=n;++i)
{
cin>>s;
sum[i][0]=0;
for(int j=1;j<=m;++j)///记录 第i个木板 前j个格子为1的个数
{
if(s[j-1]=='1') sum[i][j]=sum[i][j-1]+1;
else sum[i][j]=sum[i][j-1];
}
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)///最多刷m次
{
for(int k=1;k<=m;++k)///最多刷m个格子
{
for(int l=j-1;l<k;++l)///第j次起步最少是第j-1个格子 最多是第k-1个格子(已粉刷格数)
{
///第j次粉刷 由j-1次粉刷 l位置开始 找到其中最大的 第二次max决定粉刷1还是0
dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][l]+max(sum[i][k]-sum[i][l],k-l-sum[i][k]+sum[i][l]));
}
}
}
}
ll ans=0;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=t;++j)///刷j次
{
for(int k=1;k<=min(j,m);++k)///第i个木板涂了j次可以从第i−1个木板涂了j−k次转移过来
{
///dp[i][k][m] 第i个木板在m个格子涂k次最大
ins[i][j]=max(ins[i][j],ins[i-1][j-k]+dp[i][k][m]);
ans=max(ans,ins[i][j]);
}
}
}
cout<<ans<<endl;
return 0;
}

京公网安备 11010502036488号