给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没有M，则从串的开始算起）开始的解压结果（称为缓冲串）。 bcdcdcdcd可以压缩为bMcdRR，下面是解压缩的过程

　　另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。

　　输入仅一行，包含待压缩字符串，仅包含小写字母，长度为n。

　　输出仅一行，即压缩后字符串的最短长度。

在第一个例子中，解为aaaRa，在第二个例子中，解为bMcdRRxMcdRR。 

【限制】 

100%的数据满足：1<=n<=50 100%的数据满足：1<=n<=50

#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>using namespace std;#define MAXN 100 char S[MAXN];int len,f[MAXN][MAXN][2];bool check(int l,int r){    int mid=(l+r)>>1;    if ((r-l+1)&1) return 0;    for (int i=1; i<=mid-l+1; i++) if (S[l+i-1]!=S[mid+i]) return 0;    return 1;}int main(){    scanf("%s",S+1);    len=strlen(S+1);    for (int i=len; i>=1; i--)        for (int j=i; j<=len; j++)            {                f[i][j][0]=f[i][j][1]=j-i+1;                for (int k=i; k<j; k++)                    f[i][j][1]=min(f[i][j][1],min(f[i][k][0],f[i][k][1])+min(f[k+1][j][0],f[k+1][j][1])+1);                for (int k=i; k<j; k++)                    f[i][j][0]=min(f[i][j][0],f[i][k][0]+j-k);                if (check(i,j)) f[i][j][0]=f[i][(i+j)>>1][0]+1;                 if (j-i+1==1) f[i][j][1]=len+1;            }    printf("%d\n",min(f[1][len][1],f[1][len][0]));    return 0;}