洛谷4302 [SCOI2003]字符串折叠

题意

可以用 $x(s)$ 来表示有 $x$ 个字符 $s$ ，可以在括号内嵌套和拼接。求一个字符串的最短折叠长度。

字符串长度 $N\le 100$ 。

题解

设需要处理的字符串为 $S$ ，用 $f[l][r]$ 表示折叠 $S_l..S_r$ 的最短长度。

显然可以从两个字符串拼接而来。枚举断点 $k$ ，$f[l][r]=\min(f[l][r],f[l][k]+f[k+1][r])$ 。

也可以对当前这一段进行折叠。用 $len[i]$ 表示数字 $i$ 的位数，同样枚举断点 $k$ ，如果可以把这段用 $n$ 个 $S_l..S_k$ 来表示，则 $f[l][r]=\min(f[l][r],f[l][k]+len[\dfrac{r-l+1}{k-l+1}]+2)$

#include<bits/stdc++.h>

using namespace std;

char s[105];
int n,f[105][105],len[105];

inline bool check(int l,int r,int L,int R)
{
    for (int i=L,j=l;i<=R;i++,j++)
    {
        if (j>r) j=l;
        if (s[i]!=s[j]) return 0;
        if (i==R && j!=r) return 0;
    }
    return 1;
}

int dfs(int l,int r)
{
    if (l==r) return 1;
    int &ans=f[l][r];
    if (ans) return ans;
    ans=r-l+1;
    for (int k=l;k<r;k++)
    {
        ans=min(ans,dfs(l,k)+dfs(k+1,r));
        if (check(l,k,k+1,r)) ans=min(ans,dfs(l,k)+len[(r-l+1)/(k-l+1)]+2);
    }
    return ans;
}

signed main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    for (int i=1;i<=9;i++) len[i]=1;
    for (int i=10;i<=99;i++) len[i]=2;
    len[100]=3;
    return !printf("%d",dfs(1,n));
}