题目链接：
https://www.lydsy.com/JudgeOnline/problem.php?id=1090
https://uva.onlinejudge.org/external/16/p1630.pdf

题意：
有一个字符串，问折叠的最小长度，BZOJ1090只需输出长度，UVA1630需要输出折叠后的字符串

题解：
显然动态规划，考虑BZOJ1090的简化版本：
令$dp[i][j]$表示将$[i...j]$折叠的最小长度，那么转移分两种情况：
$dp[i][j]=dp[i][k]+dp[k+1][j]$ 直接拼上去不管折叠
$dp[i][j]=getdigit(times)+2+dp[i][k]$ （$times$是$[k+1...j]$是$[i...k]$重复几次得到的，如果不重复则为$\inf$，2是括号，$dp[i][k]$是括号里面的数）
重复得到的数瞎判一下就好了
注意这里$k$是从$i$开始循环而不是$i+1$，反例就是循环节为1的字符串（这都能80分23333），答案就是$dp[1][n]$

UVA的版本就是再开一个数组记录一下字符串就可以了。
调的时候有点心态崩，各位将就着看吧2333

BZOJ1090：

// by Balloons
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() puts("okkkkkkkk")
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)using namespace std;typedef long long LL;const int inf = 1 << 30;
const int maxn=105;char s[maxn];
int n;
int dp[maxn][maxn];int getnum(int x){int cnt=0;while(x){x/=10;++cnt;}return cnt;
}int gett(int x,int p,int y){int fx=p-x+1,fy=y-p;if(fy%fx!=0)return inf;int loop=fy/fx;for(int i=0;i<loop;i++)for(int j=0;j<fx;j++){int to=p+i*fx+j+1;if(s[x+j]!=s[to])return inf; }return loop+1;
}int main(){
//	freopen("BZOJ1090.out","w",stdout);scanf("%s",s+1);n=strlen(s+1);for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)dp[i][j]=j-i+1;for(int l=2;l<=n;l++){for(int i=1;i+l-1<=n;i++){int j=i+l-1;for(int k=i;k<j;k++){int times=gett(i,k,j);dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);if(times==inf)continue;dp[i][j]=min(dp[i][j],getnum(times)+2+dp[i][k]);}}	}printf("%d\n",dp[1][n]);return 0;
}

UVA1630：

// by Balloons
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#define mpr make_pair
#define debug() puts("okkkkkkkk")
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)using namespace std;typedef long long LL;const int inf = 1 << 30;
const int maxn=105;char s[maxn];
int n;
int dp[maxn][maxn];
string dd[maxn][maxn];int getnum(int x){int cnt=0;while(x){x/=10;++cnt;}return cnt;
}int gett(int x,int p,int y){int fx=p-x+1,fy=y-p;if(fy%fx!=0)return inf;int loop=fy/fx;for(int i=0;i<loop;i++)for(int j=0;j<fx;j++){int to=p+i*fx+j+1;if(s[x+j]!=s[to])return inf; }return loop+1;
}string tos(int tt){string ts="";while(tt){ts+=tt%10+'0';tt/=10;}reverse(ts.begin(),ts.end());return ts;
}int main(){
//	freopen("BZOJ1090.out","w",stdout);while(scanf("%s",s+1)!=EOF){memset(dp,0,sizeof dp);n=strlen(s+1);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dd[i][j].clear();for(int i=1;i<=n;i++){string tmpf="";for(int j=i;j<=n;j++){dp[i][j]=j-i+1;tmpf+=s[j];dd[i][j]=tmpf;}}for(int l=2;l<=n;l++){for(int i=1;i+l-1<=n;i++){int j=i+l-1;for(int k=i;k<j;k++){int times=gett(i,k,j);if(dp[i][j]>dp[i][k]+dp[k+1][j]){dp[i][j]=dp[i][k]+dp[k+1][j];dd[i][j]=dd[i][k]+dd[k+1][j];}if(times==inf)continue;int hh=getnum(times)+2+dp[i][k];if(dp[i][j]>hh){dp[i][j]=hh;dd[i][j]=tos(times)+"("+dd[i][k]+")";}}}	}cout<<dd[1][n]<<endl;}return 0;
}