神区间dp

设f[l][r][0]为在l到r中压缩的第一个字符为M，并且区间内只有这一个M，f[l][r][0]为在l到r中压缩的第一个字符为M，并且区间内有两个及以上的M

然后显然的转移是f[i][j][1]=min(f[i][k][0],f[i][k][1])+min(f[k+1][j][0],f[k+1][j][1])+1，f[i][j][0]=f[i][j][0],f[i][k][0]+j-k

然后考虑合并串，也就是当(l,mid),(mid+1,r)的串相等的时候，转移f[i][j][0]=f[i][(i+j)>>1][0]+1

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

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

char s[60];

bool ok(int l,int r)

{

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

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

		if(s[l+i-1]!=s[mid+i])

			return 0;

    return 1;

}

int main()

{

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

    n=strlen(s+1);

    for(int i=n;i>=1;i--)

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

		{

			f[i][j][0]=f[i][j][1]=j-i+1;

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

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

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

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

			if((j-i+1)%2==0&&ok(i,j))

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

		}

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

    return 0;

}