记录编号	577177	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[POJ 2176]折叠字符串(Folding)	最终得分	100
用户昵称	yuan	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-10-24 21:25:28	内存使用	0.00 MiB

#include<bits/stdc++.h>
#define init(x,y) memset(x,y,sizeof(x))
#define INF 0x3f3f3f3f
using namespace std;
const int N = 105;
char str[N];
int n,dp[N][N],cut[N][N],fold[N][N];
int nums (int num)
{
	int cnt = 0;
	while (num) num /= 10,++cnt;
	return cnt;
}
void check (int l,int r,int k)
{//[l,r]字符串是否可以折叠为长度为k的字符串
	if ((r - l + 1) % k) return ;
	for (int i = l;i <= r - k;++i)
		if (str[i] != str[i + k]) return ;//不合法
	int s = 2 + nums((r - l + 1) / k) + dp[l][l + k - 1];
	if (s < dp[l][r])
	{
		dp[l][r] = s;
		cut[l][r] = 0;
		fold[l][r] = k;//区间可直接折叠
	}
}

void dfs (int l,int r)
{//递归输出折叠方案
	if (!cut[l][r] && !fold[l][r])//不能折叠，原样输出
		for (int i = l;i <= r;++i) printf ("%c",str[i]);
	else
		if (cut[l][r])//有断点，分别递归两个区间
			dfs (l,cut[l][r]),dfs (cut[l][r] + 1,r);
		else//区间可直接折叠
		{
			printf ("%d(",(r - l + 1) / fold[l][r]);
			dfs (l,l + fold[l][r] - 1);//继续递归循环节
			printf (")");
		}
}
int main ()
{
	freopen ("folding.in","r",stdin);
	freopen ("folding.out","w",stdout);
	while (scanf ("%s",str + 1) != EOF)
	{
		n = strlen (str + 1);//从下标1开始存储
		init (dp,INF);init (cut,0);init (fold,0);
		for (int i = 1;i <= n;++i) dp[1][i] = i,dp[i][i] = 1;//初始化
		for (int len = 1;len <= n;++len)
		{//枚举区间长度
			for (int l = 1;l <= n - len + 1;++l)
			{//枚举区间左边界
				int r = l + len-1;//右边界
				//情况2：区间可直接折叠
				for (int k = 1;k <= (r - l + 1) / 2;++k)
					check(l,r,k);
				//情况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];
						cut[l][r] = k;//记录断点
						fold[l][r] = 0;
					}
				}
			}
		}
		//printf ("%d\n",dp[1][n]);// 最小操作次数
		dfs (1,n);//递归输出最优方案
		puts ("\n");
	}
	return 0;
}