解法:动态规划
思路:设整个字符串长度为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; }