[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) = m a x (f (i, j), f (i - 1, j - 1) + 1)$

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

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

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

我们可以用O( $nT^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^3T)$ 。
求f的3层循环中，第一层表示有1~n个木板，第二层表示会刷1~t次，在木板 $i$ 上,最多刷 $j$ 次。时间复杂度 $O(nT^2)$ 。

运行结果：
在这里插入图片描述
而对于任意一块木板而言，最涂刷 $m$ 次就可以实现不重不漏地涂刷木板，即每次只涂刷一块。for(int p=0;p<=j;p++)也可以改成for(int p=0;p<=min(j,m);p++)，因为每一块木板的最大涂刷数为 $m$ 。

这样，总体的时间复杂度降为 $O(n^4+n^2T)$ 。
运行结果：
在这里插入图片描述
代码为

    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]); }