题目描述
折叠的定义如下：
- 一个字符串可以看成它自身的折叠。记作S = S
- X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S) = SSSS…S(X个S)。
如果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<iostream>
#include<sstream> //stringstream所需的头文件
using namespace std;
int main(){
ios::sync_with_stdio(); //取消流同步是可以用的，完全和string输入输出流无关 stringstream op; //定义string输入输出流，任意变量和string互转
string p;
char s[]={"lalalavan"};
op<<s; //将char类型的字符串赋值给op
op>>p; //将op输出到p中
cout<<op.str()<<endl<<p<<endl; //两种输出方式 op.str("");
op.clear(); //对op清空必须两个都要用，可以自行尝试去掉一个，会出兮兮`～` string num="";
int n;
op<<num;op>>n; //将string类型转为int类型
cout<<n<<endl; //输出转换后的int类型
return ;
}
本题代码：
#include<bits/stdc++.h>
#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 23333
using namespace std;
int n;
string s,f[][];
il int check(int l,int r){
int sl=r-l+;
For(k,,sl>>){
if(sl%k)continue;
bool f=;
For(i,l,r-k){
if(s[i]==s[i+k])continue;
f=;
break;
}
if(f)return k;
}
return ;
}
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-){
int len=dfs(l,i).size()+dfs(i+,r).size();
if(len<ansl)mink=i,ansl=len;
}
f[l][r]+=dfs(l,mink),f[l][r]+=dfs(mink+,r);
int k=check(l,r);
if(k){
stringstream op; //定义输入输出流
op<<(r-l+)/k<<"("<<dfs(l,l+k-)<<")"; //将后面一大串依次赋给op
if(op.tellp()<f[l][r].size()) op>>f[l][r]; //比较f[l][r]和op取长度最小的
}
return f[l][r];
}
int main(){
cin>>s;
n=s.size();
For(i,,n-) For(j,,n-)f[i][j].clear();
cout<<dfs(,n-).size();
return ;
}