首页 > 代码库 > Codevs 1744 格子染色==BZOJ 1296 粉刷匠
Codevs 1744 格子染色==BZOJ 1296 粉刷匠
1744 格子染色
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 Description
有 n 条木板需要被粉刷。 每条木板被分为 m 个格子。 每个格子要被刷成红
色或蓝色。
输入描述 Input Description
Dizzy 每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个
格子最多只能被粉刷一次。 如果 Dizzy 只能粉刷 t 次，他最多能正确粉刷多少格
子？ 一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。
输出描述 Output Description
第一行包含三个整数，n m t。 接下来有n行，每行一个长度为m的字符串，‘0‘表
示红色，‘1‘表示蓝色。
样例输入 Sample Input
3 6 3
111111
000000
001100
样例输出 Sample Output
16
数据范围及提示 Data Size & Hint
1 ≤ n,m ≤ 50 ； 0 ≤ t ≤ 2500 。
分类标签 Tags 点此展开
动态规划
题解：
稍微复杂一点的划分dp
设f[i][j][k]为第i行前j个k次粉刷正确的最大值
由于每行循环使用，可以去掉第一维，但每次不要忘了清零（WA了好久）
f[j][k]=max{ f[u][j-1] + max(u+1到j的蓝色的个数，u+1到j的红颜色的个数) }
设h[i][k]为第i行分成k份的最大值
h[i][k]=f[i][m][k]
设dp[i][k]为前i行总共分成k份的最大值
dp[i][k]=dp[i-1][t-x]+h[i][x]
x表示在第i行使用x次
AC代码：
#include<cstdio>#include<algorithm>using namespace std;#define N 51#define M 2501int n,m,t,s1[N][N],s2[N][N],f[N][N],h[N][N],dp[N][M];char str[N];inline int sum1(int i,int l,int r){ return s1[i][r]-s1[i][l-1];}inline int sum2(int i,int l,int r){ return s2[i][r]-s2[i][l-1];}int main(){ scanf("%d%d%d",&n,&m,&t); for(int i=1;i<=n;i++){ scanf("%s",str+1); for(int j=1;j<=m;j++){ s1[i][j]=s1[i][j-1]; s2[i][j]=s2[i][j-1]; str[j]==‘1‘?s1[i][j]++:s2[i][j]++; } } for(int i=1;i<=n;i++){//行 for(int j=1;j<=m;j++){//前j个数 for(int k=1;k<=min(t,j);k++){//分成k份 f[j][k]=0;//注意f是每行重复使用的，需要清零！ for(int u=k-1;u<=j-1;u++){//分割点 f[j][k]=max(f[j][k],f[u][k-1]+max(sum1(i,u+1,j),sum2(i,u+1,j))); } } } for(int k=1;k<=min(t,m);k++){ h[i][k]=f[m][k]; } } for(int i=1;i<=n;i++){ for(int k=1;k<=t;k++){ for(int x=0;x<=k;x++){ dp[i][k]=max(dp[i][k],dp[i-1][k-x]+h[i][x]); } } } printf("%d",dp[n][t]); return 0;}
Codevs 1744 格子染色==BZOJ 1296 粉刷匠
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。