Folding

时间:2023-06-22 13:20:08

题意:

给定一个串,求能化成的最短循环节串(把重复字符串转化成循环节形式)

分析:

不是太好想,如果让求最短长度还好,dp[i][j],表示区间[i,j]化成的最小长度,dp[i][j]=min(dp[i][k]+dp[k+1][j]),即可但现在要求这个串不知怎么做,想着串能不能跟着转移啊,就用 str[l][r]表示区间[l,r]能化成的最短串,接着就是想怎么跟着转移了,当枚举k时,求出使得最短的k,str[l][r]=str[l][k]+str[k+1][r],再判断是否能再次循环。

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <complex>
#include <cassert>
#include <utility>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
#define lson l,m,rt<<1
#define pi acos(-1.0)
#define rson m+1,r,rt<<11
#define All 1,N,1
#define read freopen("in.txt", "r", stdin)
const ll INFll = 0x3f3f3f3f3f3f3f3fLL;
const int INF= 0x7ffffff;
const int mod = ;
char s[];
string str[][];
int dp[][];
int len(int l,int r){
for(int i=;i<=(r-l+)/;++i){
if((r-l+)%i)continue;
int f=;
for(int j=l;j+i<=r;++j)
{
if(s[j]!=s[j+i]){
f=;
break;
}
}
if(f)return i;
}
return ;
}
int dfs(int l,int r){
if(dp[l][r]!=-)return dp[l][r];
if(l==r){
dp[l][r]=;
str[l][r]=s[l];
return ;
}
int minv=INF,pos;
for(int i=l;i<r;++i){
int tmp=dfs(l,i)+dfs(i+,r);
if(tmp<minv){
pos=i;
minv=tmp;
}
}
str[l][r]=str[l][pos]+str[pos+][r];
int c=len(l,r);
if(c){
int t=(r-l+)/c;
string s1="";
while(t){
s1+=(''+t%);
t/=;
}
reverse(s1.begin(),s1.end());
s1+="("+str[l][l+c-]+")";
if(s1.size()<minv)
{
minv=s1.size();
str[l][r]=s1;
}
}
return dp[l][r]=minv;
}
int main()
{
while(~scanf("%s",s)){
memset(dp,-,sizeof(dp));
int n=strlen(s);
dfs(,n-);
cout<<str[][n-]<<endl;
}
return ;
}