首页 > 代码库 > 【Luogu1947】粉刷匠
【Luogu1947】粉刷匠
先直接抛题解，等下在整理啦QwQ
我们先不管列，考虑每一行，很容易想到设f[i][j]表示**当前这一行**前i个数涂j次色所能正确涂色的最多格子数
再枚举一个k(j≤k≤i)，考虑当前第k个格子到第i个格子的情况
我们要分情况讨论：
1. 第i个格子必须正确的刷，那么意味着k~i所刷的颜色必须是与i相同的颜色。我们用sum来表示k~i中与i颜色相同的格子个数，那么就可以递推：
$F[i][j]=max{F[k-1][j-1]+sum}(j≤k≤i)$
2. 第i个格子错误地刷，那么意味着k~i所刷的颜色必须是与i相反的颜色（总共只有两种颜色嘻嘻嘻），仍然用sum可以递推：
$F[i][j]=max{F[k-1][j-1]+i-k+1-sum}(j≤k≤i)$
以上两个取最大值即可。
但是，这道题到这里当然还没有做完——还有列没考虑呢！
其实很简单，我们记g[i][j]表示第i行涂j次色最多能正确涂的格子数，而题目说最多能涂t次色，是不是很容易想到背包问题！
至此就结束了，当然也有不少小的细节就见程序吧（解释上面应该差不多了，故代码就不注释了）
//F[i][j]//1. F[k-1][j-1]+r//2. F[k-1][j-1]+i-k+1+r//r=k~i与i相同颜色的//最后做背包 #include<cstdio>#include<cstring>#define MAX(x,y) (x>y?x:y)#define MIN(x,y) (x<y?x:y)const int N=55,T=2505;int n,m,t;int b[N][N],f[N][T],mx[N],g[N][T],dp[T];int main(){ scanf("%d%d%d",&n,&m,&t); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%1d",&b[i][j]); if(j==1||b[i][j]!=b[i][j-1]) mx[i]++; } for(int l=1;l<=n;l++) { memset(f,0,sizeof(f)); for(int i=1;i<=m;i++) { for(int j=1;j<=mx[l];j++) { int r=0; for(int k=i;k>=j;k--) { if(b[l][k]==b[l][i]) r++; f[i][j]=MAX(f[i][j],f[k-1][j-1]+r); f[i][j]=MAX(f[i][j],f[k-1][j-1]+i-k+1-r); } g[l][j]=MAX(g[l][j],f[i][j]); } } } for(int i=1;i<=n;i++) for(int j=t;j>=1;j--) for(int k=1;k<=MIN(j,mx[i]);k++) dp[j]=MAX(dp[j],dp[j-k]+g[i][k]); printf("%d",dp[t]);}
【Luogu1947】粉刷匠
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。