Description
给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小
写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没
有M，则从串的开始算起）开始的解压结果（称为缓冲串）。 bcdcdcdcd可以压缩为bMcdRR，下面是解压缩的过程
另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。
Input
输入仅一行，包含待压缩字符串，仅包含小写字母，长度为n。
Output
输出仅一行，即压缩后字符串的最短长度。
Sample Input
bcdcdcdcdxcdcdcdcd
Sample Output
12
HINT
在第一个例子中，解为aaaRa，在第二个例子中，解为bMcdRRxMcdRR。
【限制】
100%的数据满足：1<=n<=50 100%的数据满足：1<=n<=50
题解:
标签害人....差点就真的写了区间DP.....其实不用,还好有人和我写一样的...
我们明确:我们只需要知道M的位置即可确定状态
所以我们定义f[i][j]为前i个字符,M在j这个位置时的最小长度
考虑从f[i]->f[i+1]
显然我们可以直接加上原字符串的一个 f[i+1][j]=min(f[i][j]+1)
或者我们可以新建一个M f[i][i]=min(f[i][j]+1)
也可以弄一个R,相当于选定i和i+1这个位置作对称 f[i+i-j][j]=min(f[i][j]+1) 前提得满足(S[j]-S[i])==(S[i+1]+S[i+i-j])
这个判等可以预处理出来
1 #include <algorithm> 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #define RG register 8 #define il inline 9 using namespace std; 10 const int N=205; 11 int f[N][N],can[N][N];char s[N]; 12 bool check(int i,int j){ 13 int p1=i-j+1,p2=i+1; 14 for(int k=1;k<=j;k++) 15 if(s[p1]!=s[p2])return false; 16 else p1++,p2++; 17 return true; 18 } 19 void work() 20 { 21 scanf("%s",s+1); 22 int n=strlen(s+1); 23 for(int i=1;i<=n;i++){ 24 for(int j=2;i-j>=0 && i+j<=n;j++){ 25 if(check(i,j))can[i][j]=true; 26 } 27 } 28 memset(f,127/3,sizeof(f)); 29 f[0][0]=0; 30 for(int i=0;i<n;i++){ 31 for(int j=0;j<=i;j++){ 32 f[i][i]=min(f[i][i],f[i][j]+1); 33 f[i+1][j]=min(f[i+1][j],f[i][j]+1); 34 if(can[i][i-j]) 35 f[i+i-j][j]=min(f[i+i-j][j],f[i][j]+1); 36 } 37 } 38 int ans=N; 39 for(int i=0;i<=n;i++) 40 if(f[n][i]<ans) 41 ans=f[n][i]; 42 printf("%d ",ans); 43 } 44 45 int main() 46 { 47 freopen("compress.in","r",stdin); 48 freopen("compress.out","w",stdout); 49 work(); 50 return 0; 51 }