用记忆化搜索实现的动态规划…

$f[l,r]$表示区间$[l,r]$的最短折叠长度。

那么显然$f[l,r]=min(r-l+1,f[l,k]+f[k+1,r]) (l \leq k <r)$

还有一种情况，就是$[k+1,r]$是$[l,k]$重复多次形成的……这样的话就要再来一个方程了

$f[l,r]=min(f[l,r], 2+f[l,k]+get(\frac{r-k}{k-l+1}+1))$

$get$的意思就是一个函数，求一个数字占多少字符。

感谢黄学长给我的提示，用记忆化搜索实现。

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int f[111][111]; //[l,r]
bool v[111][111];
char s[111];int n;
inline bool j(int a,int b,int c,int d) {
	int modlen=b-a+1,len=d-c+1;
	if(len%modlen!=0)return 0;
	for (int i=c;i<=d;++i) {
		if(s[i]!=s[(i-c)%modlen+a])return 0;
	}return 1;
}
inline int u(int x){
	int r=0;while(x)x/=10,r++;
	return r;
}
inline int g(int l,int r) {
	if(l==r)return f[l][r]=1;
	if(v[l][r])return f[l][r];
	v[l][r]=1;f[l][r]=r-l+1;
	for (int k=l;k<r;++k) {
		int k3=g(l,k);
		f[l][r]=min(f[l][r],k3+g(k+1,r));
		if(j(l,k,k+1,r)) f[l][r]=min(f[l][r],2+k3+u((r-k)/(k-l+1)+1));
	} return f[l][r];
}
int main(){scanf("%s",s);n=strlen(s);
	printf("%d\n",g(0,n-1));
}