题目

　　给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小

写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没

有M，则从串的开始算起）开始的解压结果（称为缓冲串）。 bcdcdcdcd可以压缩为bMcdRR，下面是解压缩的过程



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

输入格式

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

输出格式

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

输入样例

bcdcdcdcdxcdcdcdcd

输出样例

12

提示

在第一个例子中，解为aaaRa，在第二个例子中，解为bMcdRRxMcdRR。

【限制】

100%的数据满足：1<=n<=50 100%的数据满足：1<=n<=50

题解

我们可以看做最左端有一个M

我们设\(f[l][r][0|1]\)表示区间\([l,r]\)在开头有M的情况下，区间内有\((1)\)或没有\((0)\)M的情况下的最短串

如果\([l,r]\)区间呈现\(AA\)形式，就可以令

然后枚举区间断点：

对于\(1\)的转移，我们枚举中间的M

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#define LL long long int

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");

using namespace std;

const int maxn = 55,maxm = 100005,INF = 1000000000;

int f[maxn][maxn][2],n;

char s[maxn];

bool check(int l,int r){

	if ((r - l + 1) & 1) return false;

	int mid = l + ((r - l + 1) >> 1) - 1;

	for (int i = 0; l + i <= mid; i++) if (s[l + i] != s[mid + 1 + i])

		return false;

	return true;

}

int main(){

	scanf("%s",s + 1); n = strlen(s + 1);

	fill(f[0][0],f[0][0] + 2 * maxn * maxn,INF);

	for (int i = 1; i <= n; i++) f[i][i][0] = 1;

	for (int len = 2; len <= n; len++){

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

			int j = i + len - 1;

			if (check(i,j)) f[i][j][0] = f[i][i + ((j - i + 1) >> 1) - 1][0] + 1;

			for (int k = i; k < j; k++)

				f[i][j][0] = min(f[i][j][0],f[i][k][0] + j - k);

			for (int k = i; k < j; k++)

				f[i][j][1] = min(f[i][j][1],min(f[i][k][1],f[i][k][0]) + 1 + min(f[k + 1][j][0],f[k + 1][j][1]));

		}

	}

	printf("%d\n",min(f[1][n][0],f[1][n][1]));

	return 0;

}