题目传送门
思考过程&具体做法： 明显的dp题，考虑如何表示状态。首先自然想到用dp[i][j]表示i到j这一段压缩后的最短长度，后面还要加一维 bool t 来表示这段中是否有M。如何转移请见代码注释。
代码：
#include <bits/stdc++.h> using namespace std; int l; int f[60][60][2],mark[60][60][2]; char s[60]; bool same(int a,int b) { int len=b-a+1; if(len%2==1) return 0; for(int i=0;i<len/2;i++) if(s[a+i]!=s[a+len/2+i]) return 0; return 1; } int dp(int a,int b,int t) { int tmp=b-a+1; if(tmp==1) return 1; if(mark[a][b][t]) return f[a][b][t]; mark[a][b][t]=1; if(t) for(int i=a;i<b;i++) tmp=min(tmp,dp(a,i,1)+dp(i+1,b,1)+1);//中间有M，分为两段压缩，中间还要加一个M（就是那个+1），否则两段会互相影响 for(int i=a;i<b;i++) tmp=min(tmp,dp(a,i,t)+b-i);//也可以只压缩一段 if(same(a,b)) tmp=min(tmp,dp(a,(a+b)>>1,0)+1);//如果能分为前后完全相同的两段，后面一段可以用R表示（那个+1） return f[a][b][t]=tmp; } int main() { scanf("%s",s+1); l=strlen(s+1); printf("%d\n",dp(1,l,1)); return 0; }