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

 

艹二维做法艹了好久，竟然还过样例了还有60（惊）

果然还是数据太水了

正解的三维做法非常巧妙

dp[x][y][1\0]表示[x,y]区间内是否有M。默认x-1前面跟着一个M

枚举断点k

dp[x][y][1]就可以从k划分的两个区间的0\1状态转移了。毕竟中间有M了可以为所欲为（雾）

dp[x][y][0]就只能从0的转移过来了。注意如果[x,y]可以从中间一分为二相同的话，还要加一个状态转移

 

 

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 char a[150]; 6 int dp[150][150][2],n; 7 int check(int x,int y) 8 { 9     int mid=(x+y)/2;10     for (int i=0;i