...
题目:
题意:
给出一个较长的字符串,要求我们按照规则进行化简,使得其长度最短
分析:
直接使用分治的思想,对于区间l−r,我们枚举一个分界点,求出如何分才能使该区间的长度最短
而对于化简,我们可以考虑r−l+1的约数,因为想要化简就必须能整除该区间的长度,然后模拟尝试是否可行即可
代码:
// luogu-judger-enable-o2
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define LL long long
#define LZX IMU
using namespace std;
inline LL read() {
LL d=0,f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}
return d*f;
}
string ss[105][105],s;
int f[105][105];
int dec(int l,int r)
{
int w=r-l+1;
for(int i=1;i<=w/2;i++)
{
if(w%i) continue;
int tf=0;
for(int j=l;j+i<=r;j++) if(s[j]!=s[j+i]) {tf=1;break;}
if(!tf) return i;
}
return -1;
}
int dfs(int l,int r)
{
if(l==0&&r==1)
{
l=l;
int c=1+1;
}
if(f[l][r]) return f[l][r];
if(l==r) {ss[l][r]=s[l];f[l][r]=1;return 1;}
int len=99999999,k;
for(int i=l;i<r;i++)
{
int ll=dfs(l,i)+dfs(i+1,r);
if(len>ll) len=ll,k=i;
}
ss[l][r]=ss[l][k]+ss[k+1][r];
f[l][r]=len;
int d=dec(l,r);
if(d==-1) return f[l][r];
string sy;
int md=(r-l+1)/d;
while(md) sy.push_back(md%10+'0'),md/=10;
reverse(sy.begin(),sy.end());
sy=sy+"("+ss[l][l+d-1]+")";
if(sy.size()<f[l][r]) f[l][r]=sy.size(),ss[l][r]=sy;
return f[l][r];
}
int main()
{
cin>>s;
dfs(0,s.size()-1);
cout<<ss[0][s.size()-1];
return 0;
}