Luogu | P4170 [CQOI 2007] 涂色 | 动态规划 | 区间 / 记忆化搜索


Description

假设你有一条长度为 $5$ 的木版,初始时没有涂过任何颜色。

你希望把它的 $5$ 个单位长度分别涂上红、绿、蓝、绿、红色,用一个长度为 $5$ 的字符串表示这个目标: RGBGR

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

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


Input Format

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


Output Format

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


Input Sample

Sample 01

AAAAA

Sample 02

RGBGR


Output Sample

Sample 01

1

Sample 02

3


Data Range

$1 \le N \le 50$。


Solution

考虑区间动态规划。设 $F[i][j]$ 为涂完字符串 $[i,j]$ 的最小步数。则分以下三种情况:

  • s[i] = s[j],因为 ij 都是当前串最靠边的位置,所以可以考虑在最底层从 i 涂到 j-1 的时候多涂一格而不需要多的步数。转移为 $\min(F[i+1][j] , F[i][j-1])$。
  • s[i] ≠ s[j],枚举中间分隔的点 k,转移为 $\min(F[i][k] + F[k+1][j])$。
  • i == j,$F[i][j] = 1$。

注意初值。


Code

#include<cstdio>
#include<cstdlib>
#include<cstring>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

inline void Read(int &x){
    x=0; char ch=0; while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return;
}

int S[105][105];

char str[105];

int MemSearch(int L,int R){
    if(L==R) return S[L][R]=1;
    if(S[L][R]) return S[L][R];
    S[L][R]=0x7f7f7f7f;
    if(str[L]==str[R])
        return S[L][R]=min(MemSearch(L+1,R),MemSearch(L,R-1));
    else
        rep(k,L,R-1)
            S[L][R]=min(S[L][R],MemSearch(L,k)+MemSearch(k+1,R));
    return S[L][R];
}

int main(){
    scanf("%s",str+1);
    printf("%d\n",MemSearch(1,strlen(str+1)));
    return 0;
}