PhantasmDragon 's Blog
Stay Determined!
主页
分类
Templates
Solutions
Life
标签
归档
关于本蒟蒻
友链
My Note
Include/hdhd Dalao
Leanote BBS
Leanote Github
Proudly powered by
Leanote
Theme by ©
mrbird
文章 - [动态规划][SCOI2009]粉刷匠
Dark
[动态规划][SCOI2009]粉刷匠
动态规划
发布于
2018-03-23
149人围观 0条评论
动态规划
发表于
2018-03-23
149人围观 0条评论
题目传送门:https://www.luogu.org/problemnew/show/P4158 ---------- ####题目描述 windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。 windy每次粉刷,只能选择一条木板上一段连续的格子,然后涂上一种颜色。 每个格子最多只能被粉刷一次。 如果windy只能粉刷 T 次,他最多能正确粉刷多少格子? 一个格子如果未被粉刷或者被粉刷错颜色,就算错误粉刷。 ####输入格式: 第一行包含三个整数,N M T。 接下来有N行,每行一个长度为M的字符串,'0'表示红色,'1'表示蓝色。 ####输出格式: 包含一个整数,最多能正确粉刷的格子数。 ---------- ###题解: 一个矩阵?我们先不考虑多维的情况,先从简单的想起. 当只有一行的时候,我们设定f[i][j]为前i格涂j次能正确涂色的最大格子数. 枚举一个断点k,我们就有: $f[i][j]=\max(f[k][j-1]+max([k+1,r]))$ 其中,max([k+1,r])表示[k+1,r]这个区间中较多的那一种颜色,可以用前缀和O(1)查询。 对于没一个n,我们都算出第n行(一整行!)涂y次能得到的最大正确数,记录在g[n][y]; 题目要求最多能够涂T次,那么相当于把这T次分配给每一行,要求最大总和,显然转化为了一个背包模型! 所以,我们再进行一次动态规划,dp[i][j]表示前i行涂j次能获得的最大正确数,我们就有: $dp[i][j]=max(dp[i-1][j-y]+g[i][y])$ 问题就<del>轻松</del>地解决了!! ---------- 贴上代码: 代码#include<cstdio> #include<cstdlib> #include<algorithm> #include<memory.h> #define maxn 100 #define maxm 5000 using namespace std; int f[maxn][maxm],g[maxn][maxm],dp[maxn][maxm],sum[maxn][maxn]; int n,m,t; int main() { scanf("%d%d%d",&n,&m,&t); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int t; scanf("%1d",&t); sum[i][j]=sum[i][j-1]+t; } } for(int r=1;r<=n;r++) { memset(f,0,sizeof(f)); for(int k=1;k<=t;k++) { for(int i=1;i<=m;i++) { for(int j=0;j<i;j++) { f[i][k]=max(f[i][k],f[j][k-1]+max(sum[r][i]-sum[r][j],i-j-(sum[r][i]-sum[r][j]))); } //printf("%d ",f[i][k]); if(i==m) g[r][k]=f[i][k]; } //printf("\n"); } } for(int i=1;i<=n;i++) { for(int j=t;j>=1;j--) { for(int y=1;y<=j;y++) { dp[i][j]=max(dp[i][j],dp[i-1][j-y]+g[i][y]); } } } printf("%d",dp[n][t]); }
上一篇:
[动态规划]矿工配餐
下一篇:
[动态规划]花店橱窗布置
0
赞
提交评论
立即登录
,发表评论
没有帐号?
立即注册
0
条评论
More...
没有帐号?立即注册