题目描述

折叠的定义如下：

1. 一个字符串可以看成它自身的折叠。记作S = S
2. X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S) = SSSS…S(X个S)。

3. 如果A = A’, B = B’，则AB = A’B’ 例如，因为3(A) = AAA, 2(B) = BB，所以3(A)C2(B) = AAACBB，而2(3(A)C)2(B) = AAACAAACBB

   给一个字符串，求它的最短折叠。例如AAAAAAAAAABABABCCD的最短折叠为：9(A)3(AB)CCD。

输入输出格式

输入格式：

仅一行，即字符串S，长度保证不超过100。

输出格式：

仅一行，即最短的折叠长度。

输入输出样例

输入样例#1： 

NEERCYESYESYESNEERCYESYESYES

输出样例#1： 

14

说明

一个最短的折叠为：2(NEERC3(YES))

 

Solution：

　　本题考试时没搞出来。（话说老余$AK$了！，自己还是个蒟蒻'!`～`!`）

　　就是一个区间$DP$，我这里用记忆化搜索来实现。

　　巧妙运用一下字符串$string$类型。定义状态$f[i][j]$表示区间$[i,j]$折叠后的最短字符串，那么当$l==r$时，显然$f[l][r]==s[l]$，搜索时枚举断点递归，找到使原串折叠后的长度最短的断点，然后枚举折叠的长度，这里用到了$stringstream$（字符串输入输出流）定义中间变量$op$，这样就可以简单的进行字符串的赋值，每一次$f[l][r]$赋为$f[l][r],op$中长度最短的一个（代码中的$op.tellp()$返回的是当前$put$流指针的位置（类似的还有$tellg$，返回$get$流指针的位置），可以理解为$op$的尾指针位置，即它的长度）。

　　这样写的好处是简洁而且能简单输出折叠后的字符串（一模一样的题，只是输出的是字符串，洛谷搜：$UVA1630\;Folding$，$STL$大法好！）。

　　此时先为不会$stringstream$的小伙伴们，安利一波（我测试的代码）：

#include
      
       #include
       
          //stringstream所需的头文件using namespace std;int main(){    ios::sync_with_stdio(0);  //取消流同步是可以用的，完全和string输入输出流无关        stringstream op;  //定义string输入输出流，任意变量和string互转    string p;    char s[12]={
    "lalalavan"};     op<
        
         >p;  //将op输出到p中    cout<
         
          <
          
           <
           
<
            
             >n; //将string类型转为int类型 cout<
             
              <
             
            
          
         
        
       
      

 

 

 

本题代码：

 

#include
      
       #define il inline#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)#define Min(a,b) ((a)>(b)?(b):(a))#define INF 23333using namespace std;int n;string s,f[105][105];il int check(int l,int r){    int sl=r-l+1;    For(k,1,sl>>1){        if(sl%k)continue;        bool f=1;        For(i,l,r-k){            if(s[i]==s[i+k])continue;            f=0;            break;        }        if(f)return k;    }    return 0;}il string dfs(int l,int r){    if(!f[l][r].empty())return f[l][r];    if(l==r)return f[l][r]=s[l];    int mink,ansl=INF;    For(i,l,r-1){        int len=dfs(l,i).size()+dfs(i+1,r).size();        if(len
       
        >f[l][r];  //比较f[l][r]和op取长度最小的    }    return f[l][r];}int main(){    cin>>s;    n=s.size();    For(i,0,n-1) For(j,0,n-1)f[i][j].clear();    cout<