题目链接：
区间(DP)。
设(f_{[l][r]})？
但是转移时如果加一个(R)则无法知道上一个(M)在什么地方。
所以设(f_{[l][r][0/1]})表示区间([l,r])，有一个(M)在开头，中间是否有其他(M)时的最小长度。
那么有转移方程：
[f_{[l][r][0]}=min_{i=l}^{r-1}{f_{[l][i][0]}+r-i}
]
由前后两段组成，后面不能有(M)，所以长度不变。
[f_{[l][r][0]}=f_{[l][(l+r)>>1][0]}+1
]
当区间([l,r])是两个相同子串相连时可以用(R)表示。可以暴力判断
[f_{[l][r][1]}=min_{l=i}^{r-1}{min(f_{[l][i][0]},f_{[l][i][1]})+min(f_{[i+1][r][0]},f_{[i+1][r][1]})}
]
直接由两段拼成，每一段必须有(M)。
时间复杂度 (O(n^3))
#include <cstdio>
#include <cstring>
inline int Min(int a,int b){return a<b?a:b;}
int n,f[55][55][2];
char s[55];
inline bool Dou(int l,int r)//判断区间[l,r]是否是两个相同子串相连
{
if((r-l+1)&1)return false;
for(int i=l,j=(l+r+1)>>1;j<=r;++i,++j)
if(s[i]!=s[j])return false;
return true;
}
int DP(int l,int r,int m)
{
if(f[l][r][m])return f[l][r][m];
if(l==r)return f[l][r][m]=2;
int Res=0x3f3f3f3f;
if(!m)
{
if(Dou(l,r))Res=Min(Res,DP(l,(l+r)>>1,0)+1);
for(int i=l;i<r;++i)Res=Min(Res,DP(l,i,0)+r-i);
}
else
for(int i=l;i<r;++i)
Res=Min(Res,Min(DP(l,i,0),DP(l,i,1))+Min(DP(i+1,r,0),DP(i+1,r,1)));
return f[l][r][m]=Res;
}
int main()
{
scanf("%s",s+1),n=strlen(s+1);
printf("%d
",Min(DP(1,n,0),DP(1,n,1))-1);
return 0;
}