洛谷P4170 [CQOI2007]涂色 题解

题目链接：P4170 [CQOI2007]涂色

题意：

假设你有一条长度为 $5$ 的木板，初始时没有涂过任何颜色。你希望把它的 $5$ 个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为 $5$ 的字符串表示这个目标：$\texttt{RGBGR}$。

每次你可以把一段连续的木板涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木板涂成 $\texttt{RRRRR}$，第二次涂成 $\texttt{RGGGR}$，第三次涂成 $\texttt{RGBGR}$，达到目标。

用尽量少的涂色次数达到目标。

考虑区间dp

设 $dp[i][j]$ 表示涂区间 $[i,j]$ 的最小花费

当 $i=j$ 时，有

$$dp[i][j]=1$$

当 $i\ne j$ 时，

• 若 $a[i]=a[j]$ ，此时只需要 $[i+1,j]$ 或 $[i,j-1]$ 首次涂的时候多涂一格即可

  $$dp[i][j]=\min(dp[i+1][j],dp[i][j-1])$$

• 若 $a[i]\ne a[j]$ ， $a[i],a[j]$ 都可以尝试向内扩展，显然 $[i,j]$ 首次涂会涂两种颜色，考虑枚举其断点 $k$

  $$dp[i][j]=\min(dp[i][j],dp[i][k]+dp[k+1][j])$$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(55)

int n,dp[N][N];
char a[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> (a+1);
    n=strlen(a+1);
    memset(dp,0x3f,sizeof(dp));
    for(int i=1; i<=n; i++)dp[i][i]=1;
    for(int len=2; len<=n; len++)
        for(int i=1,j=i+len-1; i+len-1<=n; i++,j++)
        {
            if(a[i]==a[j])dp[i][j]=min(dp[i+1][j],dp[i][j-1]);
            else for(int k=i; k<j; k++)
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
        }
    cout << dp[1][n] << endl;
    return 0;
}