本文主要是介绍P7537 [COCI2016-2017#4] Rima，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
由于题目涉及到后缀，不难想到用 trie 树处理。
将每个字符串翻转插入 trie，后缀就变成了前缀，方便处理。
条件 LCS ( A , B ) ≥ max ( ∣ A ∣ , ∣ B ∣ ) − 1 \text{LCS}(A,B) \ge \max(|A|,|B|)-1 LCS(A,B)≥max(∣A∣,∣B∣)−1，说明 ∣ ∣ A ∣ − ∣ B ∣ ∣ ≤ 1 \left||A|-|B|\right|\le1 ∣∣A∣−∣B∣∣≤1。
所以两个字符串押韵当且仅当在 trie 树上二者是父子或兄弟关系。
考虑树型 DP，设 f i f_i fi 表示 i i i 所代表的字符串在序列最右边的最长序列长度， v a l i val_i vali 表示节点 i i i 是否（1/0）有单词， s z i = ∑ x ∈ s o n i v a l x sz_i=\sum\limits_{x\in son_i}val_x szi=x∈soni∑valx。
显然有转移 f i = max x ∈ s o n x ( f x ) + s z i − 1 + v a l i f_i=\max\limits_{x\in son_x}(f_x)+sz_i-1+val_i fi=x∈sonxmax(fx)+szi−1+vali。
如果 v a l i = 0 val_i=0 vali=0，说明都没有字符串， f i = 0 f_i=0 fi=0。
更新答案时，记录儿子 f s o n i f_{son_i} fsoni 的最大和次大，再加上剩余儿子和自己的 v a l val val。（感性理解，一条链只有两个位置是“自由”的，由此设出 DP 状态）
本题卡空间，所以建 trie 树时要动态开点。
具体实现参见代码。
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+10;
int cnt=1,n,f[N],ans;
char a[N];
struct node
{vector<pair<int,int> > son;int fa,val;
}tr[N];
void insert(int rt,char a[],int len)
{for(int i=0;i<len;i++){int x=a[i]-97;for(auto j:tr[rt].son){if(j.first==x){rt=j.second;goto a;}}tr[rt].son.push_back(make_pair(x,++cnt));rt=tr[rt].son.back().second;a:;}tr[rt].val++;
}
void dfs(int rt)
{int aa=0,bb=0,x=0,y=0,sum=0;for(auto i:tr[rt].son){dfs(i.second);sum+=tr[i.second].val;f[rt]=max(f[rt],f[i.second]);if(f[i.second]>aa){bb=aa;aa=f[i.second];y=x;x=tr[i.second].val;}else if(f[i.second]>bb) bb=f[i.second],y=tr[i.second].val;}f[rt]+=sum-x;if(!tr[rt].son.size()) ans=max(ans,tr[rt].val);else ans=max(ans,aa+bb-x-y+sum+tr[rt].val);if(!tr[rt].val) f[rt]=0;else f[rt]++;
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",a);int len=strlen(a);reverse(a,a+len);insert(1,a,len);}dfs(1);cout<<ans;
}
这篇关于P7537 [COCI2016-2017#4] Rima的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
