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
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59