自动搬运

查看原文

来自洛谷，原作者为

	ADay Overrated.

搬运于2025-08-24 22:33:45，当前版本为作者最后更新于2021-10-20 22:10:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

更逊的阅读体验

模拟赛原题，赛时一直在肝另一题就没做

Solution

求最长子序列的题，显然可以 $\mathsf{dp}$，方程为 $f_i=\max\limits_{j<i}\{f_j\}+1(x_j\,\text{为}\,x_i\,\text{的前缀和后缀})$。

考虑怎么判断一个字符串为另一个字符串的的前缀和后缀。我们有一个很妙的做法：把字符串 $s_{1\cdots n}$ 正反合在一起组成 $n$ 个字符二元组，即 $(s_1,s_n)(s_2,s_{n-1})\dots(s_n,s_1)$，那么这样就只用判断 $x_j$ 组成的二元组是否是 $x_i$ 的二元组的前缀就好了。

对于这些二元组，我们可以直接建 $\mathsf{Trie}$，把每个字符串的二元组当成一个字符集为 $26\times26$ 的字符串插入，在插入的过程中如果当前节点是某个字符串的结尾就直接进行 $\mathsf{dp}$，并在插入完时的结点记录此字符串编号即可。

关于实现，由于这棵 $\mathsf{Trie}$ 的每条边有两个字符 ab，我们可以把它转化为一个数 (a-'A')*26+(b-'A')，并用 $\mathsf{unordered\_map}$ 实现动态开点的子节点列表。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int n,m,ans,tot,f[N],id[N];char s[N];
unordered_map<int,unordered_map<int,int>>g;//Trie
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);m=strlen(s+1);
        int u=0;
        for(int j=1;j<=m;j++){
            f[i]=max(f[i],f[id[u]]+1);
            int w=(s[j]-'A')*26+s[m-j+1]-'A';//正反合并
            if(g[u].find(w)==g[u].end())g[u][w]=++tot;//动态开点
            u=g[u][w];
        }if(id[u])f[i]=max(f[i],f[id[u]]+1);
        ans=max(ans,f[i]);id[u]=i;
    }printf("%d\n",ans);
    return 0;
}

最后祝各位 $\texttt{CSP2021 rp++!}$