admin 管理员组

文章数量: 1184232

P4158[SCOI2009]粉刷匠

题目描述

windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。
windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。
如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？
一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。

输入输出格式

输入格式：
第一行包含三个整数，N M T。
接下来有N行，每行一个长度为M的字符串，'0'表示红色，'1'表示蓝色。
输出格式：
包含一个整数，最多能正确粉刷的格子数。

代码

\(f[i][j]\)的数组来表示前i条木板粉刷j次的情况下能正确粉刷的最大格子数
\(g[i][j][k]\)来表示第i条木板上粉刷j次涂了前k个格子的情况下能正确粉刷的最大格
\(sum[i][j]\)数组来记录第i木板区间j前的蓝色格子数，红色格子：区间长度减去蓝色格子
dp方程：
\(g[i][j][k]=max(g[i][j][k],g[i][j-1][q]+max(sum[i][k]-sum[i][q],k-q-sum[i][k]+sum[i][q]));\)
\(f[i][j]=max(f[i][j],f[i-1][j-k]+g[i][k][m]);\)

   #include<bits/stdc++.h>using namespace std;int n,m,t;const int maxn=50+5,maxm=2500+5;int f[maxn][maxm];int g[maxn][maxm][maxn];int sum [maxn][maxn];int main(){scanf("%d%d%d",&n,&m,&t);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){int a;scanf("%1d",&a);sum[i][j]=sum[i][j-1];if(a==1)sum[i][j]++;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int k=1;k<=m;k++)for(int l=j-1;l<k;l++)g[i][j][k]=max(g[i][j][k],g[i][j-1][l]+max(sum[i][k]-sum[i][l],k-l-sum[i][k]+sum[i][l]));for(int i=1;i<=n;i++)for(int j=1;j<=t;j++)for(int k=0;k<=min(j,m);k++)f[i][j]=max(f[i][j],f[i-1][j-k]+g[i][k][m]);int ans=0;for(int i=0;i<=t;i++)ans=max(ans,f[n][i]);printf("%d",ans);return 0;}

转载于:.html

本文标签： P4158SCOI2009粉刷匠

版权声明：本文标题：P4158[SCOI2009]粉刷匠 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.roclinux.cn/p/1698024320a283182.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。