这一题，唔……区间DP
用\(f_{i,j,k}\)表示\(i\rightarrow j\)这一串字符中，能否（\(k\)）加入R的最短字符串
如果，我们能够在这一段文字中加R，那么就是这样
对于所有的串，都能够这样：
\[f_{i,j,k}=\min\{f_{i,l,k}+1+j-l-1\}\]如果串的长度为偶数，那么就能这样
\[f_{i,j,k}=f_{i,i+\frac{j-i+1}{2},0}+1\]枚举\(l\)然后答案就是这三者中的最小值
再加上记忆化搜索就能够AC了
AC-Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=55;
bool vis[MAXN][MAXN][2];
int f[MAXN][MAXN][2];
char data[MAXN];
bool compare(int s1,int s2)
{
int len=s2-s1;
for (int i=0;i<len;i++)
if (data[s1+i]!=data[s2+i])
return false;
return true;
}
int dp(int l,int r,bool add)
{
int len=r-l+1;
int ret=len;
if (l==r)
return 1;
if (vis[l][r][add])
return f[l][r][add];
vis[l][r][add]=true;
for (int i=l;i<r;i++)
{
if (add)
ret=min(ret,dp(l,i,1)+dp(i+1,r,1)+1);
ret=min(ret,dp(l,i,add)+r-i);//dp(l,i,add)+1+r-i-1
}
if (len%2==0)
if (compare(l,l+len/2))
ret=min(ret,dp(l,l+len/2-1,0)+1);
return f[l][r][add]=ret;
}
int main()
{
scanf("%s",data+1);
printf("%d\n",dp(1,strlen(data+1),1));
return 0;
}