02 区间DP：涂色

[CQOI2007] 涂色

题目描述

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

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

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

输入格式

输入仅一行，包含一个长度为 $n$ 的字符串，即涂色目标。字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。

输出格式

仅一行，包含一个数，即最少的涂色次数。

样例 #1

样例输入 #1

AAAAA

样例输出 #1

1

样例 #2

样例输入 #2

RGBGR

样例输出 #2

3

提示

$40\%$ 的数据满足 $1\le n\le 10$。

$100\%$ 的数据满足 $1\le n\le 50$。

区间dp的plus版：我愿称之为完全区间dp

把从i到j的所有情况列在对应表格中；我们发现：

GBBR可以分解为（此处为常规区间dp）

G+BBR

GB+BR

GBB+R

这3种情况（隔板法分割把区间一分为二）

当然也会出现不用讨论分隔直接完成的：比如RGBBR相对于RGBB就可以相等；

首先赋初值，对角线为初值，赋1；

然后我们可以手动填上第二个斜线上的数字，我们可以看见，因为s[2]==s[3]，所以只要在刷一个的时候范围刷大刷到另一个所在位置即可，故dp[ i ][ j ] = =dp[ i-1 ][ j ]==dp[i+1][ j ]

所以当区间 i~j 首末数字相等时，可以直接 ”刷过来“ ，即等于下面的或者左边的；

当区间 i~j 首末数字不相等时候，则用区间dp对当前空格位置代表的字符串切分，比出一个最小值

例如GBBR可以分解为（此处为常规区间dp）

G+BBR dp[ 1 ][ 1 ]+dp[ 2 ][ 4 ]

GB+BR dp[ 1 ][ 2 ]+dp[ 3 ][ 4 ]

GBB+R dp[ 1 ][ 3 ]+dp[ 4 ][ 4 ]

这3种情况（隔板法分割把区间一分为二）

因此：dp[ 1 ][ 4 ]=max{ dp[ 1 ][ 1 ]+dp[ 2 ][ 4 ] , dp[ 1 ][ 2 ]+dp[ 3 ][ 4 ] , dp[ 1 ][ 3 ]+dp[ 4 ][ 4 ] };

由此我们得到对于任意一个dp[ i ][ j ]的状态转移方程

dp[ i ][ j ]= case1: dp[ i-1 ][ j ] or dp[i+1][ j ] ( if s[ i ]==s[ j ] )

case 2: maxE(k from i to j-1){dp[ i ][ k ]+dp[ k+1 ][ j ]} ( if s[ i ]!=s[ j ] )

由此我们就可以很愉快的敲代码了

#include <iostream>
#include <cstring>
#include <algorithm>
#define maxsize 55
using namespace std;
int dp[maxsize][maxsize]={0};

int main()
    {
        string s;
        memset(dp,0x3f,sizeof(dp));
        cin>>s;
        for(int i=0;i<s.size();i++)
            dp[i][i]=1;
        for(int p=0;p<s.size()-1;p++)//注意见下
        for(int i=0,j=p+1;j<s.size();i++,j++)
            {
                if(s[i]==s[j])dp[i][j]=dp[i+1][j];
                else 
                {
                    dp[i][j]=dp[i][i]+dp[i+1][j];
                    for(int k=i;k<j;k++)
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
                }
            }
        cout<<dp[0][s.size()-1]<<endl;
        return 0;
    }

这里的p是指对第2~n个主对角线方向的斜线的遍历（第一个斜线即主对角线已经遍历过了）