给出一个长度为n的序列({a_i})，定义一个收缩的序列变为原序列的方式为
- 如果该收缩序列只有一个字符，原序列即该个字符。
- 如果一个收缩序列由多个收缩序列，那么分别对各个收缩序列进行解压，即原序列
- 如果收缩序列形如(n(S))，意为收缩序列S重复n次（注意，n为数字，转化成字符需要占空间），解压即把该序列重复n次。
请找到一个最短的收缩序列，解压后正好为序列({a_i})，(nleq 100)。
解
显然问题具有区间划分性，因为几个收缩序列可以组成一个收缩序列，于是可以考虑区间递推，设(f[i][j])表示合并([i,j])后的最短的字符串，（接下来的+为字符串的相加，比较大小为字符串长度的比较，不知道意思查string的用法),首先区间合并性可以
[f[i][j]=min_{k=i}^{j-1}{f[i][k]+f[k+1][j]}
]
现在来考虑循环节的问题，循环节可以(O(n^2))枚举，但是所有的循环节中必然是最短的循环节最优（感性理解一下），设最短循环节为k，有
[f[i][j]=min(f[i][j],to\_string(k)+"("+f[i][k-1]+")")
]
边界：(f[i][i]=a_i)
答案：(f[1][n])
参考代码：
string 阶段实现
#include <iostream>
#include <cstdio>
#define il inline
#define ri register
using namespace std;
string s,dp[101][101],lsy;
il string To(int);
il int xh(int,int);
int main(){
cin>>s;
for(int i(1);i<=s.size();++i)
dp[i][i].push_back(s[i-1]);
for(int i,j(1),k;j<=s.size();++j)
for(i=j-1;i;--i){
for(k=i;k<j;++k){
lsy=dp[i][k]+dp[k+1][j];
if(!dp[i][j].size()||dp[i][j].size()>lsy.size())
dp[i][j]=lsy;
}k=xh(i,j);
if(k){
lsy=To((j-i+1)/k)+"("+dp[i][i+k-1]+")";
if(lsy.size()<dp[i][j].size())
dp[i][j]=lsy;
}
}cout<<dp[1][s.size()].size();
return 0;
}
il string To(int x){
string ans;int w(1);while(w<=x)w*=10;w/=10;
while(w)ans.push_back(x/w+48),x%=w,w/=10;
return ans;
}
il int xh(int l,int r){
int len(r-l+1);
for(int i(1),j;i<=(len>>1);++i){
if(len%i)continue;
for(j=l;j<=r-i;++j){
if(s[j-1]==s[j+i-1])continue;
break;
}if(j>r-i)return i;
}return 0;
}
string dfs实现
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#define il inline
#define ri register
using namespace std;
string s,dp[101][101],
dfs(int,int);
il int cycle(int,int);
il string To_string(int);
int main(){
cin>>s;
for(int i(1);i<=s.size();++i)
dp[i][i].push_back(s[i-1]);
cout<<dfs(1,s.size())<<endl;
return 0;
}
il string To_string(int x){
string ans;int w(1);
while(w<=x)w*=10;w/=10;
while(w)ans.push_back(x/w+48),
x%=w,w/=10;return ans;
}
il int cycle(int l,int r){
int len(r-l+1);
for(int i(1),j;i<=(len>>1);++i){
if(len%i)continue;
for(j=l;j<=r-i;++j){
if(s[j-1]==s[j+i-1])continue;
break;
}if(j>r-i)return i;
}return 0;
}
string dfs(int l,int r){
if(dp[l][r].size())return dp[l][r];
string lsy;
for(int k(l);k<r;++k){
lsy=dfs(l,k)+dfs(k+1,r);
if(lsy.size()<dp[l][r].size()
||!dp[l][r].size())dp[l][r]=lsy;
}int k(cycle(l,r));
if(k){
lsy=dfs(l,l+k-1);
lsy=To_string((r-l+1)/k)+"("+lsy+")";
if(lsy.size()<dp[l][r].size())dp[l][r]=lsy;
}return dp[l][r];
}
char数组实现
#include <iostream>
#include <cstdio>
#include <cstring>
#define il inline
#define ri register
#define intmax 0x7fffffff
using namespace std;
struct String{
char s[111];int len;
il void read(){
scanf("%s",s);
len=strlen(s);
}
}s,dp[101][101],lsy;
il int xh(int,int);
int main(){
s.read();
for(int i(1);i<=s.len;++i)
dp[i][i].s[0]=s.s[i-1],
dp[i][i].len=1;
for(int i,j(1),k,l;j<=s.len;++j)
for(i=j-1;i;--i){
dp[i][j].len=intmax;
for(k=i;k<j;++k)
if(dp[i][k].len+dp[k+1][j].len<dp[i][j].len)
dp[i][j].len=dp[i][k].len+dp[k+1][j].len,l=k;
strcpy(dp[i][j].s,dp[i][l].s);
strcat(dp[i][j].s,dp[l+1][j].s);
l=xh(i,j);if(l){
sprintf(lsy.s,"%d",(j-i+1)/l),strcat(lsy.s,"(");
strcat(lsy.s,dp[i][i+l-1].s),strcat(lsy.s,")");
lsy.len=strlen(lsy.s);
if(lsy.len<=dp[i][j].len)
dp[i][j]=lsy;
}
}printf("%s",dp[1][s.len].s);
return 0;
}
il int xh(int l,int r){
int L(r-l+1);
for(int i(1),j;i<=(L>>1);++i){
if(L%i)continue;
for(j=l;j<=r-i;++j){
if(s.s[j-1]==s.s[j+i-1])continue;
break;
}if(j>r-i)return i;
}return 0;
}