Description：

给字符串压缩，可以用 $M$ 标记串的开始，用 $R$ 重复到上一个 $M$ 的解压结果，问一个字符串最少能压缩到多长。

$1\le n\le 50$

Solution：

一个比较好想的区间 $DP$ 思路是用 $f[l][r]$ 表示从 $l$ 到 $r$ 的字符串压缩的最小长度，转移为 $f[l][r]=\min(f[l][k],f[k+1][r])$ 和 $l[l][r]=\min(f[l][r],f[l][\frac{l+r}2]+2)(s[l,mid]=s[mid+1,r])$ 。

但是这样在 $l$ ~ $\frac{l+r}2$ 中有 $M$ 时最后的 $R$ 并不会将 $l$ ~ $\frac{l+r}2$ 重复，而是会将中间的 $M$ 到最后重复，要解决这个问题也很简单，只要强行保证 $l$ ~ $\frac{l+r}2$ 中没有 $M$ 即可，于是设 $f[i][j][0/1]$ 表示从 $l$ 到 $r$ 中间能否有 $M$ ，注意这个状态代表在这之前强行补上一个 $M$ ，因为如果没有 $M$ 的话 $R$ 直接从开头开始，转移要么是分成两段，即 $(M)\times\times R\times\times$ ，由于状态的定义，只有在第三维为 $1$ 时才能转移，要么是这一段可以分解成两段一样的，转移为 $f[l][r][0/1]=f[l][\frac{l+r}2]+1$ ，然而还有第三种转移，就是如果后面直接复制没有任何操作的话，中间那个 $M$ 就不用加了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXL 51

char c[MAXL];

int f[MAXL][MAXL][2];

bool equ(int l,int r)

{

	int len = (r - l + 1);

	if(len % 2 == 1)return false;

	len /= 2;

	for(int i = l;i <= l + len - 1;++i)

	{

		if(c[i] != c[i + len])return false;

	}

	return true;

}

int dp(int l,int r,int t)

{

	if(l == r)return 1;

	if(f[l][r][t] != -1)return f[l][r][t];

	int ans = (r - l + 1);

	if(t)for(int i = l;i < r;++i)ans = min(ans,dp(l,i,t) + dp(i + 1,r,t) + 1);

	for(int i = l;i < r;++i)ans = min(ans,dp(l,i,t) + r - i);

	if(equ(l,r))ans = min(ans,dp(l,(l + r) >> 1,0) + 1);

	return (f[l][r][t] = ans);

}

int main()

{

	scanf("%s",c + 1);

	memset(f,-1,sizeof(f));

	int l = strlen(c + 1);

	cout << dp(1,l,1) << endl; 

	return 0;

}