题目

题目描述

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

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

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

输入格式

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

输出格式

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

输入输出样例

输入 #1

AAAAA

输出 #1

1

输入 #2

RGBGR

输出 #2

3

说明/提示

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

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

题解

我们把问题抽象成为一个长度为$n$的字符串$s$，字符串中每种字母代表一种颜色。 用 $dp[x][y]$表示让区间 $[x,y]$ 满足条件的最小次数。然后我们按照区间长度从小到大枚举每一个区间。

如果s[x] == s[y]

我们可以先把$[x,y]$整体涂成一个颜色，然后再去处理$[x+1,y-1]$。对应的转移为:

dp[x][y]=min(dp[x][y],dp[x+1][y−1]+1)

或者对于区间$[x,y-1]$，因为$x$是最边上的位置，所以最优情况下，一定可以第一个涂$x$位置，这样我们可以让这次涂色延长到$y$，这样实际上$y$就顺带满足条件了，区间$[x+1,y]$也是同样原理，对应的转移为:

dp[x][y]=min(dp[x][y−1],dp[x+1][y])

如果s[x] != s[y]

那么实际上$x$和$y$没有关系，所以我们可以把区间分成两部分来完成，一部分包含 $x$，一部分包含$y$。对应的转移为:

∀ x≤k<y,dp[x][y]=min(dp[x][y],dp[x][k]+dp[k+1][y])

代码

按照刚才的分析，可以得到如下代码：

#include <iostream> #include <string> #include <algorithm> #include <cstring> using namespace std; const int inf = 0x3f3f3f3f; int dp[55][55]; int main(){ string s; cin>>s; memset(dp,0x3f,sizeof(dp)); for(int i=0;i<s.size();i++){ dp[i][i]=1; } for(int l=2;l<=s.size();l++){ for(int i=0;i<s.size()-l+1;i++){ int j=i+l-1; if(s[i]==s[j]){ if(l==2){ dp[i][j]=1; } else{ dp[i][j]=min(min(dp[i+1][j],dp[i][j-1]),dp[i+1][j-1]+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[0][s.size()-1]<<endl; return 0; }