神区间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;
}