想法是区间 dp，然后分类讨论寻找第一个折叠之后一定不亏的点来判断是否需要增加折叠花费，但是 WA 了。

#include<bits/stdc++.h>
using namespace std;
string s;
int n,f[5200][5200];
inline bool check(int lef1,int rig1,int lef2,int rig2){
	for(;lef1<=rig1;lef1++,lef2++){
		if(s[lef1]!=s[lef2])return false;
	}
	return true;
} 
int main(){
	cin>>s;n=s.size();s='*'+s;
	for(int len=1;len<=n;len++){
		for(int lef=1;lef<=n-len+1;lef++){
			int rig=lef+len-1;
			f[lef][rig]=rig-lef+1;
			for(int k=lef+rig>>1;k<rig;k++){
				if(k>=lef+rig>>1){
					if(check(2*k-rig+1,k,k+1,rig)){
						if(rig-lef+1>=3*(rig-k)&&check(3*k-2*rig+1,2*k-rig,k+1,rig)){
							if(rig-lef+1>=4*(rig-k)&&check(4*k-3*rig+1,3*k-2*rig,k+1,rig)){
								if(rig-lef+1>=5*(rig-k)&&check(5*k-4*rig+1,4*k-3*rig,k+1,rig)){
									f[lef][rig]=min(f[lef][rig],f[lef][k]);
								}//>=5
								else{
									if(rig-k==1)f[lef][rig]=min(f[lef][rig],f[lef][k-3]+4);
									else f[lef][rig]=min(f[lef][rig],f[lef][k]);	
								}
							}//=4
							else{
								if(rig-k==2)f[lef][rig]=min(f[lef][rig],f[lef][k-4]+5);
								else if(rig-k!=1)f[lef][rig]=min(f[lef][rig],f[lef][k]);
							}//=3
						}//>=3
						else{
							if(rig-k>=3)f[lef][rig]=min(f[lef][rig],f[lef][k]+3);
						}//=2
					}
				}
				f[lef][rig]=min(f[lef][rig],f[lef][k]+f[k+1][rig]);
			}
		}
	}
	cout<<f[1][n];
}