UVA11022 String Factoring 题解

Elairin176 · 2024-01-28 11:42:25 · 题解

传送门

题意

有一种对字符串的压缩方案如下：将字符串中所有相同的连续子串合并为一，直至无法继续合并。
现在给出一些字符串，要求输出对其压缩后的长度。

解法

发现本题是区间操作，所以考虑区间 dp。
我们设 f_{i,j} 为 [i,j] 区间经压缩后的长度。
那么，对于每个 f_{l,r} 有：

• 如果可以直接对 [l,r] 进行合并，那么先进行合并。
• 可以枚举中间的一个断点 k 进行合并。

我们逐个来看。

操作 1

我们这里用 KMP 预处理出 next 数组，之后判断是否存在周期。
这里显然如果 n 是 n-next_n 的倍数时存在周期，其长度为 n-next_n。其中 n 为字符串长度。
我们对 [l,r] 求 next 数组后判断即可。

操作 2

枚举断点，直接相加即可。f_{l,r}=\min\limits_{l\le k<r}f_{l,k}+f_{k+1,r}。

最终答案在 f_{1,n} 中。有些细节问题比较简单，请读者自行思考。
CODE：

//完整缺省源请见洛谷云剪贴板 jo5j6ogx
const int N=80;
string s;
int nxt[N+10],n,f[N+10][N+10];
il void getnxt(int l,int r){
    int j=0;
    for(int i=l+1;i<=r;i++){
        while(j!=0&&s[i]!=s[j+l]){
            j=nxt[j];
        }
        if(s[i]==s[l+j]){
            j++;
        }
        nxt[i]=j;
    }
}
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while(cin>>s,s!="*"){
        memset(f,0x3f,sizeof(f));
        n=s.length();
        s="="+s;
        for(int i=1;i<=n;i++){
            f[i][i]=1;
        }
        for(int len=2;len<=n;len++){
            for(int l=1;l+len-1<=n;l++){
                int r=l+len-1;
                getnxt(l,r);
                if((r-l+1)%(r-l+1-nxt[r])==0){
                    f[l][r]=_min<int>(f[l][r],f[l][r-nxt[r]]);
                }
                for(int k=l;k<r;k++){
                    f[l][r]=_min<int>(f[l][r],f[l][k]+f[k+1][r]);
                }
            }
        }
        write(f[1][n]);
        edl;
    }
    ret 0;
}