CF1789F Serval and Brain Power 题解

题目链接

点击打开链接

题目解法

好有技巧性的题（感觉 \(n\le 80\) 这个数据范围就很奇怪啊）

首先可以发现 \(k\le 3\) 是好做的，只要枚举断点，然后 \(dp\) 做一遍 \(lcs\) 即可，时间复杂度为 \(O(n^{2k+1})\)，不过严重跑不满，所以可以跑
\(k=4\) 的情况和 \(k=2\) 的情况是相同的，所以不用考虑
\(k\ge 5\) 的情况需要一个性质：一定存在一个循环节占的子序列跨度 \(\le 16\)，这是显然的，于是枚举状态，贪心匹配即可，时间复杂度为 \(O(n^22^{16})\)

感觉还是很妙的数据分治题，但我不知道 \(k\ge 5\) 的做法是如何想到的/ll

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=90;
int g[N][N],f[N][N][N];
char str[N],seq[N];
int main(){
    scanf("%s",str+1);
    int n=strlen(str+1);
    int ans=0;
    //k>=5
    int len=min(n,16);
    F(i,1,n-len+1)
        F(j,1,(1<<len)-1){
            int cnt=0;
            F(k,0,len-1) if(j>>k&1) seq[++cnt]=str[i+k];
            int cur=1,tot=0;
            F(j,1,n){
                if(seq[cur]==str[j]) cur++;
                if(cur==cnt+1) tot++,cur=1;
            }
            if(tot>1) chkmax(ans,tot*cnt);
        }
    //k=2
    F(p1,2,n){
        ms(g,0);
        g[1][p1]=0;
        F(i,1,p1-1) F(j,p1,n){
            if(str[i]==str[j]) g[i][j]++,chkmax(g[i+1][j+1],g[i][j]);
            else chkmax(g[i+1][j],g[i][j]),chkmax(g[i][j+1],g[i][j]);
            chkmax(ans,g[i][j]*2);
        }
    }   
    //k=3
    F(p1,2,n) F(p2,p1+1,n){
        F(i,1,p1-1) F(j,p1,p2-1) F(k,p2,n) f[i][j][k]=0;
        F(i,1,p1-1) F(j,p1,p2-1) F(k,p2,n){
            if(str[i]==str[j]&&str[i]==str[k]) f[i][j][k]++,chkmax(f[i+1][j+1][k+1],f[i][j][k]);
            else chkmax(f[i+1][j][k],f[i][j][k]),chkmax(f[i][j+1][k],f[i][j][k]),chkmax(f[i][j][k+1],f[i][j][k]);
            chkmax(ans,f[i][j][k]*3);
        }
    }
    printf("%d\n",ans);
    return 0;
}