居然可以嵌套…
考虑区间dp.
f[l][r]表示折叠后[l,r]这一段的最短长度
有两种转移:
- 被一个$k(l\le k<r)$分成$[l,k],[k+1,r]$合并得到.
- 被某个子串展开得到.
前者直接枚举$k$取min即可.我们考虑后者.
考虑枚举这个子串的长度$k$.如果这个子串展开能得到$[l,r]$,那么$k$一定是当前串长度($r-l+1$)的约数,且$[l..l+k-1],[l+k..l+k+k-1]..[r-k+1..r]$都是相同的.
那么,我们先判断是否是约数,然后用$[l..l+k-1]$去匹配$[l,r]$就好了,如果全部匹配,则可以展开得到$[l,r]$
约数是$O(\sqrt n)$个,所以时间复杂度上界为$O(n^2\times(n+n\times \sqrt n))=O(n^3\sqrt n)$(这是一个很松的上界,实际运行远远低于它)
最后输出路径,就枚举这两种转移,如果转移可以得到$f[l][r]$,就采用这种转移.
实现有一些细节,可见代码.(你顺便可以把这题给A了).
/**********/省略快读
#define MAXN 111
ll f[MAXN][MAXN];//f[l][r]:[l..r]
ll cost[MAXN];
char a[MAXN];
bool substr(ll sl,ll sr,ll l,ll r)//[sl..sr]展开能否得到[l...r]
{
ll len=sr-sl+1;
if((r-l+1)%len)return 0;
for(ll k=0;k<r-l+1;++k)
if(a[l+k]!=a[sl+(k%len)])return 0;
return 1;
}
void printway(ll l,ll r)//输出路径
{
if(f[l][r]==r-l+1)
{
for(ll i=l;i<=r;++i)putchar(a[i]);
return;
}
for(ll k=l;k<r;++k)
{
if(f[l][r]==f[l][k]+f[k+1][r])
{
printway(l,k);printway(k+1,r);
return;
}
if(substr(l,k,l,r)&&f[l][r]==f[l][k]+cost[(r-l+1)/(k-l+1)]+2)
{
printf("%lld(",(r-l+1)/(k-l+1));
printway(l,k);
putchar(')');
return;
}
}
}
int main()
{
for(ll i=1;i<=99;++i)//预处理每个数字的长度
{
if(i>=10)cost[i]=2;
else cost[i]=1;
}
cost[100]=3;
scanf("%s",a+1);
ll n=strlen(a+1);
for(ll i=1;i<=n;++i)f[i][i]=1;
for(ll len=2;len<=n;++len)
{
for(ll l=1;l+len-1<=n;++l)
{
ll r=l+len-1;
f[l][r]=r-l+1;
for(ll k=l;k<r;++k)
{
umin(f[l][r],f[l][k]+f[k+1][r]);//两种转移
if(substr(l,k,l,r))umin(f[l][r],f[l][k]+cost[(r-l+1)/(k-l+1)]+2);
}
}
}
//printf("%lld",f[1][n]);
printway(1,n);
return 0;
}
stO