洛谷 P4302 字符串折叠 题解

洛谷P4302
一道很水的紫题，代码贼短。
基本是区间dp的板子，判断一下什么时候可以合并即可……
需要记住的是，区间dp必须要枚举区间长度和起点，不然顺序会出错qaq（60分WA的惨痛教训）

#include<bits/stdc++.h>
using namespace std;
#define MAXN 105
#define inf 1e9+9
char s[MAXN];
int len,dp[MAXN][MAXN];
bool judge(int l,int r,int L,int R){
	if((R-L+1)%(r-l+1)) return 0;
	int le=r-l+1;
	for(int i=L+le;i<=R;i++)
	  if(s[i]!=s[l+(i-l)%le])return 0;
	return 1;
}
int minn(int x,int y){return x<y?x:y;}
int a=0;
int getlen(int x){a=0;while(x)a++,x/=10;return a;}
int main(){
	scanf("%s",s);
	len=strlen(s)-1;
	for(int i=0;i<=len;i++)
	  for(int j=0;j<=len;j++)  dp[i][j]=inf;
	for(int i=0;i<=len;i++) dp[i][i]=1;
	for(int l=1;l<=len;l++)
	  for(int i=0;i<=len-l;i++){
	  	int j=l+i;
	  	dp[i][j]=j-i+1;
	  	for(int k=i;k<j;k++){
	  		dp[i][j]=minn(dp[i][j],dp[i][k]+dp[k+1][j]);
	  		if(judge(i,k,i,j))
	  		  dp[i][j]=minn(dp[i][j],2+getlen((j-i+1)/(k-i+1))+dp[i][k]);
	  	}
	  }
	  cout<<dp[0][len]<<endl;
	  return 0;
}