洛谷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;
}