这题一看不会 在看了半天像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; }