简要题意

给出一个字符串 \(S\)，你可以进行任意次（压缩）操作，每次操作可以把字符串中连续几个相同的部分压缩成相同的一个。操作可以嵌套进行。你需要求出操作后字符串的最小长度。

多组数据。以 * 结束。

\(1 \leq |S| \leq 80\)，\(S\) 中仅包含英文大写字母。

思路

这道题直接用 KMP 不太好做，我们发现一个区间的答案可以由它的子区间合并得到。于是我们可以考虑区间 DP。

令 \(f_{i,j}\) 为区间 \([i,j]\) 的答案。

显然有 \(f_{i,i}=1\)。

则对于一个不由几个相同部分组成的区间可以枚举断点简单转移得到：

然后考虑可以压缩的区间。除了上述转移外还有额外的转移。我们令最小重复部分长度（压缩后的长度）为 \(L\)。则额外转移为：

然后考虑如何求 \(L\)。我们先求出 \([i,j]\) 之间的字符串的失配数组 \(\operatorname{fail}\)。如果 \((j-i+1) \bmod ((j-i+1)-\operatorname{fail}({j})) = 0\) 则代表可以压缩。然后 \((j-i+1)-\operatorname{fail}({j})\) 就是 \(L\) 了。至于严谨推导过程，见 OI Wiki。时间复杂度为 \(O(n)\)。

然后这道题我们就可以做到 \(O(n^3)\) 了。（据说暴力求 \(L\) 也可以过）

最后贴一下完整的转移方程（如果 LaTex 炸了可以去上面的链接里查看）：

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int f[85][85],fail[85];
bool vis[85][85];
string str;
int n;

int dp(int l,int r){
    if(vis[l][r]) return f[l][r];
    vis[l][r]=1;
    if(l==r) return f[l][r]=1;
    f[l][r]=INT_MAX;
    for(int i=l;i<r;i++){
        f[l][r]=min(f[l][r],dp(l,i)+dp(i+1,r));
    }
    for(int i=1;i<=n;i++) fail[i]=0;
    for(int i=l+1,j;i<=r;i++){
        j=fail[i-1];
        while(j&&str[l+j]!=str[i]) j=fail[l+j-1];
        if(str[l+j]==str[i]) j++;
        fail[i]=j;
    }
    if((r-l+1)%(r-l+1-fail[r]) == 0){
        f[l][r]=min(f[l][r],dp(l,l+(r-l+1-fail[r])-1));
    }
    return f[l][r];
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    while(cin>>str){
        if(str[0] == '*') break;
        memset(vis,0,sizeof(vis));
        n=str.size();str=" "+str;
        cout<<dp(1,n)<<'\n';
    }
    return 0;
}