P7537 [COCI2016-2017#4] Rima

由于题目涉及到后缀，不难想到用 trie 树处理。

将每个字符串翻转插入 trie，后缀就变成了前缀，方便处理。

条件 $\text{LCS}(A,B)\ge \max (|A|,|B|)-1$，说明 $\left||A|-|B|\right|\le 1$。

所以两个字符串押韵当且仅当在 trie 树上二者是父子或兄弟关系。

考虑树型 DP，设 $f_i$ 表示 $i$ 所代表的字符串在序列最右边的最长序列长度，$va{l}_i$ 表示节点 $i$ 是否（1/0）有单词，$s{z}_i=\sum _{x\in so{n}_i}va{l}_x$。

显然有转移 $f_i=\underset{x\in so{n}_x}{\max }(f_x)+s{z}_i-1+va{l}_i$。

如果 $va{l}_i=0$，说明都没有字符串，$f_i=0$。

更新答案时，记录儿子 $f_{so{n}_i}$ 的最大和次大，再加上剩余儿子和自己的 $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;
}