题目链接：压缩
区间动归水题。稍微有一点细节。
令\(f_{l,r}\)表示区间\([l,r]\)最短压缩长度，默认\(l\)位置之前有个\(M\)。然后就枚举一下放不放\(R\)，\(M\)放哪个位置或者不放，记忆搜很好写。
但是细节就在于，每个\(R\)的有效区间是到上一个\(M\)，所以我们枚举在哪里放\(R\)之后，左边的区间内是不能放\(M\)的。所以在状态里多加一维，表示当前这个区间内能不能放\(M\)，直接转移就行了。
下面贴代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define N 61
using namespace std;
typedef long long llg;
char s[N];
int f[N][N][2];
bool pd(int l,int r){
for(int i=l,j=r;i<r;i++,j++)
if(s[i]!=s[j]) return 0;
return 1;
}
int gi(int l,int r,bool w);
int dfs(int l,int r,bool w){
if(f[l][r][w]) return f[l][r][w];
int now=r-l+1,mid=(l+r+1)>>1;
for(int i=l+1;i<=mid;i++)
if(pd(l,i)) now=min(now,dfs(l,i-1,0)+gi(i*2-l,r,w)+1);
if(w) for(int i=l+1;i<=r;i++) now=min(now,dfs(l,i-1,1)+gi(i,r,1));
return f[l][r][w]=now;
}
int gi(int l,int r,bool w){
if(l>r) return 0; int now=r-l+1;
if(w) now=min(now,dfs(l,r,1)+1);
return now;
}
int main(){
File("a");
scanf("%s",s+1);
printf("%d",dfs(1,strlen(s+1),1));
return 0;
}
原文：http://www.cnblogs.com/lcf-2000/p/6618649.html