P4158 [SCOI2009]粉刷匠

2023-11-09 15:45

文章标签 scoi2009 p4158 粉刷

本文主要是介绍P4158 [SCOI2009]粉刷匠，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Portal.

DP。

设 $f (i, j)$ 表示前 $i$ 条木板粉刷 $j$ 次能正确粉刷的最大格子数， $g (i, j, k)$ 表示第 $i$ 条木板上粉刷 $j$ 次涂了前 $k$ 个格子能正确粉刷的最大格子数，用前缀和数组记录蓝色格子数（ $sum_{i,j}$ 表示第 $i$ 条木板到位置 $j$ 有几个蓝格子），某个区间的格子数减蓝色格子数就是红色格子数。

求能正确粉刷的最大格子数，状态转移方程为： $f(i,j)=\max(f(i,j),f(i-1,j-k)+g(i,k,M))$ 。

求 $g (i, j, k)$ 的状态转移方程，要考虑前 $r$ 个格子正确粉刷的最大格子数加上下一步正确粉刷的格子数（这里要比较一下是正确粉刷的蓝格子多还是红格子多）。
$g(i,j,k)=\max(g(i,j,k),g(i,j-1,r)+\max(sum_{i,k}-sum_{i,r},k-r-sum_{i,k}+sum_{i,r})$
代码如下：

#include <bits/stdc++.h>
using namespace std;int f[55][2505],sum[55][2505],g[55][2505][55];
char s[105];int main()
{int N,M,T,ans=0;cin>>N>>M>>T;for(int i=1;i<=N;i++) {cin>>s;sum[i][0]=0;//前缀和初始化for(int j=1;j<=M;j++){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<=T;j++)for(int k=1;k<=T;k++)for(int r=j-1;r<k;r++)//因为s数组是从下标为0开始的g[i][j][k]=max(g[i][j][k],g[i][j-1][r]+max(sum[i][k]-sum[i][r],k-r-sum[i][k]+sum[i][r]));for(int i=1;i<=N;i++)for(int j=1;j<=T;j++)for(int k=1;k<=min(j,M);k++)f[i][j]=max(f[i][j],f[i-1][j-k]+g[i][k][M]);for(int i=1;i<=T;i++) ans=max(ans,f[N][i]);cout<<ans;return 0;
}