60pts

记 $f_{l,r,0/1}$ 表示在 $[l,r]$ 区间内是否有 $M$ ,默认开头有一个 $M$ ,但是算出来会比答案大,不知道为什么

#include<bits/stdc++.h>
using namespace std;
int n;
int s[55];
int f[55][55][2];
void Init(){
	char ch=getchar();
	while('a'<=ch&&ch<='z'){
		s[++n]=ch-'a';
		ch=getchar();
	}
	return;
}
bool check(int L_1,int R_1,int L_2,int R_2){
	for(int i=0;i<R_1-L_1;i++)
		if(s[L_1+i]!=s[L_2+i])return 0;
	return 1;
}
signed main(){
	Init();
	memset(f,0x3f,sizeof f);
	for(int i=0;i<n;i++){
		for(int l=1;l+i<=n;l++){
			int r=l+i;
			f[l][r][0]=r-l+1;
			f[l][r][1]=r-l+2;
			if((i&1)&&check(l,(l+r)/2,(l+r+1)/2,r))
				f[l][r][0]=min(f[l][(l+r)/2][0]+1,f[l][r][0]);//直接加R 
			for(int k=l;k<r;k++)
				f[l][r][0]=min(f[l][r][0],f[l][k][0]+r-k);//考虑末尾的几个为直接加进去的 
			for(int k=l;k<r;k++)
				f[l][r][1]=min(f[l][r][1],min(f[l][k][0],f[l][k][1])+min(f[k+1][r][0],f[k+1][r][1])+1);//放M 
		}
	}
	cout<<min(f[1][n][0],f[1][n][1]);
	return 0;
}