给出一个长度为n的序列\(\{a_i\}\)，定义一个收缩的序列变为原序列的方式为

1. 如果该收缩序列只有一个字符，原序列即该个字符。
2. 如果一个收缩序列由多个收缩序列，那么分别对各个收缩序列进行解压，即原序列
3. 如果收缩序列形如\(n(S)\)，意为收缩序列S重复n次（注意，n为数字，转化成字符需要占空间），解压即把该序列重复n次。

请找到一个最短的收缩序列，解压后正好为序列\(\{a_i\}\)，\(n\leq 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 
    
     #include 
     
      #define il inline#define ri registerusing 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
      
       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()
       
        >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 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define il inline#define ri registerusing 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<
         
          <
          
           >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
          
         
        
       
      
     
    

char数组实现

#include 
    
     #include 
     
      #include 
      
       #define il inline#define ri register#define intmax 0x7fffffffusing 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
       
        >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;}