解法：动态规划
思路：设整个字符串长度为n。根据题意，我们可以看作在区间[1,n]之前已经放有一个字母M。那么我们就是要用一些M和R，将字符串中的重复串分割出来，并使最终压缩后的字符串尽量短，本文第一行都说了这是个区间DP了对吧。在例子bcdcdcdcdxcdcdcdcd中，cd我称之为重复串，而其中的cdcdcdcd便是题目所说的缓冲串。
个人认为呢，解题的关键便是重复串和缓冲串的寻找，由此将解题方向指向对M、R位置的寻找。所以我们仅仅需要用动态规划求出M的位置就离成功不远了。如果发现当前处理的字符串中不含M，并且左右两半是一样的，那么就在中点处放一个R并去掉后面那一半就行了。比如：cdcd>>cdRcd>>cdR
然后我们就可以定义数组f[left][right][ok]，用f来表示输入中left到right的部分字符串，如果ok=1则表示该部分字符串中有放M，若ok=0则反之。
现在来考虑考虑边界情况：
首先来#define INF 0x3f3f3f3f 弄个大数字吧(别问我为什么hhhhh)
边界条件是f[][][0]=1(只有一个字符不能放M呢，不然就更大了。你看b还要压缩吗),f[][][1]=INF
这边界条件怎么出来的应该一个个自己想一会都想得出吧……
我懒就懒得解释了……再说了你们那么聪明肯定会懂的对吧！
最后print出一个最小值就OK了。
程序自己看咯，建议对照着上面的文字看，更容易看得懂。
Code:
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 55
#define INF 0x3f3f3f3f
using namespace std;
int f[maxn][maxn][2],n;
char st[maxn];
bool bo(int left,int right) {
if ((right-left+1)&1)return false;
int m=(left+right)>>1;
for (int i=left; i<=m; i++)if(st[i]!=st[m+i-left+1])return false;
return true;
}
int dp(int left,int right,bool ok) {
if (f[left][right][ok]<INF)return f[left][right][ok];
int len=right-left+1;
if (len==1) return ok?f[left][right][ok]=INF:f[left][right][ok]=1;
int m=(left+right)>>1;
if (ok) {
for (int i=left; i<right; i++) {
f[left][right][ok]=min(f[left][right][ok],dp(left,i,1)+1+dp(i+1,right,1));
f[left][right][ok]=min(f[left][right][ok],dp(left,i,0)+1+dp(i+1,right,1));
f[left][right][ok]=min(f[left][right][ok],dp(left,i,1)+1+dp(i+1,right,0));
f[left][right][ok]=min(f[left][right][ok],dp(left,i,0)+1+dp(i+1,right,0));
}
return f[left][right][ok];
}
if (bo(left,right))f[left][right][ok]=dp(left,m,0)+1;
for (int i=left; i<right; i++)
f[left][right][ok]=min(f[left][right][ok],dp(left,i,0)+right-i);
return f[left][right][ok];
}
int main() {
memset(f,INF,sizeof(f));
scanf("%s",st+1); n=strlen(st+1);
printf("%d\n",min(dp(1,n,0),dp(1,n,1)));
return 0;
}
