[SCOI2009]粉刷匠 牛客DP入门

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

0x00 题目来源

[SCOI2009]粉刷匠

0x10 Tag

线性DP、区间DP

0x20 题目描述

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

输入格式
3 6 3
111111
000000
001100
一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。

---

0x30 思路与算法

0x31 化简成简单的DP

如果将题目化简为N条木板，每个木板作为一个整体涂色，只能粉刷T次，求正确粉刷的木板数。显而易见的线性DP对不对。
即得状态转移式，如下:$$f(i,j)=max(f(i,j),f(i-1,j-1)+1)$$

其中$i$代表第$i$号木板，$j$代表粉刷的轮次（第$j$次粉刷）。

那么，本题的问题是，在木板被细化成块之后，如何处理木板与木板之间的状态转移。首先，从题设可知，每块木板可以被多次粉刷，我们假设第第$i$号木板被粉刷了$p$次，而这块木板贡献了$g$个正确涂刷的方块。则状态转移式为：$$f(i,j)=max(f(i,j),f(i-1,j-p)+g)$$

原先简化条件中，刷木板最多会贡献1的正确涂刷数，最多刷一次。
而在题设条件下，我们设最多贡献g的正确涂刷数,最多刷p次。

我们可以用O($n{T}^2$)的循环实现状态转移，现在的问题是，如何求g？

0x32 求g

对于g，其意义是第$i$号木板最大的正确涂抹数。所以我们不妨设其状态为第$i$条木板上粉刷$j$次涂了前$k$个格子。
那么它的状态转移表达式为$$g(i,j,k)=max(g(i,j,k),g(i,j-1,q)+max(B_{interval},R_{interval}))$$

我们设$q$为上一次涂抹已经涂了$q$格子，$B/R_{interval}$为$q$到$k$这一段区间中任意同色格子最大数。

0x33 代码实现

声明

const int MAXN=55;
const int MAXT=2510;
int f[MAXN][MAXT];
int g[MAXN][MAXN][MAXN];
int blue[MAXN][MAXN];
int red[MAXN][MAXN];

blue与red分别为第$i$号木板中对应的蓝色和红色的前缀和数组。f,g为两个动态转移状态数组。
初始化

        if(ch=='1') {blue[i][j]=blue[i][j-1]+1;red[i][j]=red[i][j-1];}else {red[i][j]=red[i][j-1]+1;blue[i][j]=blue[i][j-1];   }

输入的时候顺便求以下前缀和，以便求区间数量。

0x34 完整代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
const ll INF = 0x3f3f3f3f;
// <------------------------------->
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define HACK freopen("test.in", "r", stdin);freopen("test.out", "w", stdout);
#define RT double rtime = 1.0 * clock() / CLOCKS_PER_SEC;cout<<"\nRuntime: "<<rtime<< " s.\n";
#define debug(x) cout<<"target is "<<x<<endl
#define debug_arr(arr) for(auto x:arr) cout<<x<<" "; cout<<"\n";
//#define LOCAL_JUDGE
//#pragma GCC optimize(2)
// <------------------------------->
const int MAXN=55;
const int MAXT=2510;
int f[MAXN][MAXT];
int g[MAXN][MAXN][MAXN];
int blue[MAXN][MAXN];
int red[MAXN][MAXN];
// <------------------------------->
int main()
{IOS;#ifdef LOCAL_JUDGEHACK;#endifint n,m,t;cin>>n>>m>>t;char ch;for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){cin>>ch;if(ch=='1') {blue[i][j]=blue[i][j-1]+1;red[i][j]=red[i][j-1];}else {red[i][j]=red[i][j-1]+1;blue[i][j]=blue[i][j-1];   }}for(int i=1;i<=n;i++)for(int j=1;j<=t;j++)for(int k=0;k<=m;k++)for(int q=0;q<k;q++){g[i][j][k]=max(g[i][j][k],g[i][j-1][q]+max(blue[i][k]-blue[i][q],red[i][k]-red[i][q]));}// dp gfor(int i=1;i<=n;i++)for(int j=1;j<=t;j++)for(int p=0;p<=j;p++){f[i][j]=max(f[i][j],f[i-1][j-p]+g[i][p][m]); }// dp fint ans=0;for(int i=1;i<=t;i++) ans=max(ans,f[n][i]);cout<<ans;#ifdef LOCAL_JUDGERT;#endifreturn 0;
}

0x35 优化

我们聚焦在状态转移方程之上，代码如下

    for(int i=1;i<=n;i++)for(int j=1;j<=t;j++)for(int k=0;k<=m;k++)for(int q=0;q<k;q++){g[i][j][k]=max(g[i][j][k],g[i][j-1][q]+max(blue[i][k]-blue[i][q],red[i][k]-red[i][q]));}// dp gfor(int i=1;i<=n;i++)for(int j=1;j<=t;j++)for(int p=0;p<=j;p++){f[i][j]=max(f[i][j],f[i-1][j-p]+g[i][p][m]); }

求g的4层循环中，第一层表示有1~n个木板，第二层表示会刷1~t次，k最多刷满m格，q最多刷k-1格。时间复杂度$O(n^{3}T)$。
求f的3层循环中，第一层表示有1~n个木板，第二层表示会刷1~t次，在木板$i$上,最多刷$j$次。时间复杂度$O(n{T}^2)$。

运行结果：

而对于任意一块木板而言，最涂刷$m$次就可以实现不重不漏地涂刷木板，即每次只涂刷一块。for(int p=0;p<=j;p++)也可以改成for(int p=0;p<=min(j,m);p++)，因为每一块木板的最大涂刷数为$m$。

这样，总体的时间复杂度降为$O(n^4+n^{2}T)$。
运行结果：

代码为

    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int k=0;k<=m;k++)for(int q=0;q<k;q++){g[i][j][k]=max(g[i][j][k],g[i][j-1][q]+max(blue[i][k]-blue[i][q],red[i][k]-red[i][q]));}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]); }

---

0x40 另

=)

这篇关于[SCOI2009]粉刷匠 牛客DP入门的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---