[SCOI2007]压缩

Time Limit:1000MS  Memory Limit:165536K
Total Submit:18 Accepted:10

Description

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

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

Input

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

Output

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

Sample Input

bcdcdcdcdxcdcdcdcd

Sample Output

12

Hint

在第一个例子中，解为aaaRa，在第二个例子中，解为bMcdRRxMcdRR。
【限制】
50%的数据满足：1<=n<=20
100%的数据满足：1<=n<=50
100%的数据满足：1<=n<=50

Source
其实是蛮简单的一道题啊，就是Dp啊，但是各种东西太纠结了。。我WA了N次。。。

晕死，状态定义就是（l,r,t）表示l到r的字串，t表示中间能否放M。。关键就是如果后面放了R的话中间就不能放M了晕死。。WA了这么多次，不想活了囧。。
Code：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxl=100;
char M[maxl];
bool S[maxl][maxl][2]={0};
int Dp[maxl][maxl][2];
bool Match(int p,int Len,int s)
{
if(Len%s)return false;
rep(i,Len)if(M[p+i]!=M[p+i%s])return false;
return true;
}
inline int Update(int&x,int c){x=min(x,c);}
int dfs(int l,int r,bool t)
{
int&x=Dp[l][r][t];if(S[l][r][t]) return x;
S[l][r][t]=true;int Len=r-l+1;x=Len;
if(Len==1)return x;
if(t)for(int k=l;k<r;k++)Update(x,dfs(l,k,1)+1+dfs(k+1,r,1));
for(int k=l;k<r;k++)Update(x,dfs(l,k,t)+r-k);
if(Len%2==0&&Match(l,Len,Len/2)) Update(x,dfs(l,l+Len/2-1,0)+1);
return x;
}
int main()
{
//freopen("in","r",stdin);
cin>>M;
cout<<dfs(0,strlen(M)-1,1)<<endl;
}