SCOI2003 字符串折叠 & NEERC2002 Folding 题解

两题大同小异，一个是输出最短解，一个是构造最短方案。

考虑区间 DP。

可得方程 (dp_{l,r}=min(dp_{l,k}+dp{k+1,r},dp_{l,r}))，这是单独合并，不折叠的情况。

若折叠呢？我们枚举折叠里的循环长度，计算其重复次数 (num)，可得 (dp_{l,r}=min(dp_{l,r},num 的长度+2+min(dp_{l,num+l-1},i)))。

如何处理方案呢？

将上面的 DP 方程套一下即可。

时间复杂度 (O(n^4))。

可以在枚举折叠里的循环长度时仅枚举到 (sqrt{len})，于是可以优化到 (O(n^3sqrt{n}))。

#include<bits/stdc++.h>
using namespace std;
int dp[110][110],n,h,t,num;
string g[110][110];
char st[110];
unordered_map<string,bool> myd;
string substr(int l,int r) {
	string ret;
	for(int i=l; i<=r; i++)
		ret=ret+st[i];
	return ret;
}//截取自 l 到 r 的字符串
int work(int x) {
	int num=0;
	while(x) {
		num++;
		x/=10;
	}
	return num;
}//求数字 x 的位数
bool check(int l,int r,int x) {
	myd.clear();
	h=l,t=l+x-1;
	string st=substr(h,t);
	myd[st]=1,num=1;
	t+=x,h+=x;
	while(t<=r) {
		st=substr(h,t);
		if(!myd[st])
			return 0;
		num++;
		h+=x,t+=x;
	}
	return 1;
}//check l~r 是否有一个长为 x 的循环节
string ch_to_st(int num) {
	string ret;
	int numb[5],tot=0;;
	while(num) {
		numb[++tot]=num%10;
		num/=10;
	}
	for(int i=tot;i>=1;i--)
	    ret=ret+(char)(numb[i]+'0');
	return ret;
}/将 num 转化成字符串
int main() {
	while(scanf("%s",st+1)!=EOF) {
		n=strlen(st+1);
		//printf("%d
",n);
		memset(dp,0x7f7f7f7f,sizeof dp);
		for(int i=1; i<=n; i++) {
			dp[i][i]=1;
			g[i][i]=st[i];
		}
		for(int len=2; len<=n; len++)
			for(int l=1; l<=n-len+1; l++) {
				int r=l+len-1;
				for(int k=l; k<r; k++)
					if(dp[l][k]+dp[k+1][r]<dp[l][r]) {
						dp[l][r]=dp[l][k]+dp[k+1][r];
						g[l][r]=g[l][k]+g[k+1][r];
					}//普通转移
				for(int i=1; i*i<=len; i++)
					if(len%i==0) {
						if(check(l,r,i)&&work(num)+2+min(dp[l][i+l-1],i)<dp[l][r]) {
							dp[l][r]=work(num)+2+min(dp[l][i+l-1],i);
							g[l][r]=ch_to_st(num)+'('+(dp[l][i+l-1]<i?g[l][i+l-1]:substr(l,i+l-1))+')';
						}
						if(check(l,r,len/i)&&work(num)+2+min(dp[l][len/i+l-1],len/i)<dp[l][r]) {
							dp[l][r]=work(num)+2+min(dp[l][len/i+l-1],len/i);
							g[l][r]=ch_to_st(num)+'('+(dp[l][len/i+l-1]<len/i?g[l][len/i+l-1]:substr(l,len/i+l-1))+')';
						}
					}//枚举循环节进行转移
			}　　　　　
		cout<<g[1][n]<<endl;
	}
	while(1)
	    puts("Dua!");
}