CF1789F

Miraik · 2023-02-26 13:22:50 · 题解

数据范围很小，不妨考虑对于 k 值不同的情况设计不同的方案。

对于 k \le 3 的情况，我们有一个暴力的想法：枚举 k-1 个终点，如 k=3 时枚举 x,y，然后计算 s[1,x]，s[x+1,y]，s[y+1,n] 的最长公共子序列。

这部分复杂度似乎是 O(n^5) 的，但是实际上它远远跑不满，因为你枚举 x 和 y 有 \frac{1}{2} 的常数，把序列划出的三部分平方起来至少有 \frac{1}{27} 的常数，所以它至少有一个 \frac{1}{54} 的常数，并不会超时。

你再考虑对于 k \ge 4 的情况设计方案。首先你会发现 k=2 严格包含 k=4，所以我们只需要考虑 k \ge 5 的情况。

在 n\le 80，k \ge 5 时，我们需要注意到：对于任意 T ，必然存在某个 i 满足 T' 为 s[i,i+15] 的子序列。因为如果不满足，那么每个子序列的跨度超过 16，其需要的总长度就会超过 16 \times 5=80，显然不合法。

于是枚举 i，状压后 16 位的状态，再到原序列检查一遍即可。这部分的复杂度为 O(n^2 \times 2^{16})。可以做到更优复杂度，但是这个已经足以通过。

#include<bits/stdc++.h>
using namespace std;
int n,m,f[85][85],g[85][85][85],ans; char s[85],t[85];
inline int lcs2(int l1,int r1,int l2,int r2){
    for(int i=l1-1;i<=r1+1;i++)
        for(int j=l2-1;j<=r2+1;j++)
            f[i][j]=0;
    for(int i=l1;i<=r1;i++)
        for(int j=l2;j<=r2;j++)
            f[i][j]=max(max(f[i][j-1],f[i-1][j]),f[i-1][j-1]+(s[i]==s[j]));
    return f[r1][r2];
}
inline int lcs3(int l1,int r1,int l2,int r2,int l3,int r3){
    for(int i=l1-1;i<=r1+1;i++)
        for(int j=l2-1;j<=r2+1;j++)
            for(int k=l3-1;k<=r3+1;k++)
                g[i][j][k]=0;
    for(int i=l1;i<=r1;i++)
        for(int j=l2;j<=r2;j++)
            for(int k=l3;k<=r3;k++)
                g[i][j][k]=max(max(g[i][j][k-1],max(g[i][j-1][k],g[i-1][j][k])),g[i-1][j-1][k-1]+(s[i]==s[j]&&s[i]==s[k]));
    return g[r1][r2][r3];
}
inline int check(){
    int ans=0;
    for(int i=1,j=1;i<=n;i++)
        if(s[i]==t[j]){
            j++;
            if(j==m+1) j=1,ans++;
        }
    return ans>1?ans*m:0;
}
int main(){
    scanf("%s",s+1); n=strlen(s+1);
    for(int i=1;i<n;i++) ans=max(ans,2*lcs2(1,i,i+1,n));
    for(int i=1;i<n;i++)
        for(int j=i+1;j<n;j++)
            ans=max(ans,3*lcs3(1,i,i+1,j,j+1,n));
    for(int i=1;i<=n;i++){
        for(int sta=1;sta<(1<<16);sta+=2){
            m=0;
            for(int j=0;j<16&&i+j<=n;j++)
                if(sta&(1<<j)) t[++m]=s[i+j];
            ans=max(ans,check());
        }
    }
    printf("%d\n",ans);
    return 0;
}