标签：记忆化搜索,DP
题目描述
给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没有M，则从串的开始算起）开始的解压结果（称为缓冲串）。
bcdcdcdcd可以压缩为bMcdRR，下面是解压缩的过程：
已经解压的部分 解压结果 缓冲串
b b b
bM b
bMc bc c
bMcd bcd cd
bMcdR bcdcd cdcd
bMcdRR bcdcdcdcd cdcdcdcd
另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。
输入输出格式
输入格式：
输入仅一行，包含待压缩字符串，仅包含小写字母，长度为n。
输出格式：
输出仅一行，即压缩后字符串的最短长度。
输入输出样例
输入样例#1：
aaaaaaa
输出样例#1：
5
输入样例#2：
bcdcdcdcdxcdcdcdcd
输出样例#2：
12
说明
在第一个例子中，解为aaaRa，在第二个例子中，解为bMcdRRxMcdRR。
【限制】
50%的数据满足：1<=n<=20
100%的数据满足：1<=n<=50
分析：
Mark数组用来记忆化存储
每次DP传递的第三个参数t从来记录这段区间内是否存在M
如果t=1，可以分成两段进行压缩，且两段t=1，两段的中间要加一个M，否则前一段会对后一段造成影响
当然也可以只压缩前一段
如果分成等长的两段完全相等且每一段都没放M，可以把后一段换成R
Code
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
const int maxn=106;
int f[maxn][maxn][2];
bool mark[maxn][maxn][2];
char s[maxn];
inline bool same(int a,int b){
int temp=b-a+1;
if(temp&1)return 0;
rep(i,a,(a+b)>>1)
if(s[i]!=s[i+(temp>>1)])return 0;
return 1;
}
int dp(int a,int b,bool t)
{
int temp=b-a+1;
if(temp==1)return 1;
if(mark[a][b][t])return f[a][b][t];
mark[a][b][t]=1;
if(t)
rep(i,a,b-1)temp=min(temp,dp(a,i,1)+dp(i+1,b,1)+1);
rep(i,a,b-1)temp=min(temp,dp(a,i,t)+b-i);
if(same(a,b))temp=min(temp,dp(a,(a+b)>>1,0)+1);
return f[a][b][t]=temp;
}
int main()
{
cin>>s;
int len=strlen(s);
cout<<dp(0,len-1,1)<<endl;
return 0;
}
