[第四场T4]Rima

题目描述

Adrian对单词押韵很感兴趣。如果两个单词的最长公共后缀的长度与两个单词中较长那个的长度一样，或者等于较长单词的长度减一，则这两个单词押韵。换句话说，如果A,B的最长公共后缀LCS（A，B）≥max（|A|，|B|）-1，则A和B押韵。

有一天，在阅读一套短篇小说时，他决定创造出能够使每两个相邻单词押韵的最长的单词序列，序列中的每个单词只能出现一次。但是Adrian已经厌倦了这个任务，所以他决定回去读小说，并要求你代替他解决这个任务。

输入

第一行输入包含整数N（1≤N≤5*1e5）。表示单词的个数。

接下来N行每行包含一个只由小写英文字母组成的字符串。表示可以用于组成序列的单词。数据保证每个单词都是不同的，保证所有单词的长度之和不超过3*1e6。

输出

输出一个整数。表示单词序列的最长长度。

解题思路

很明显倒着插入建立字典树。

然后呢？

算答案需要遍历一遍这棵树。

所以是一个树上DP，我们用DP[u]表示以编号u的节点结尾的单词后最多能接上的单词数量。

该节点对答案的贡献则就是两个最大的儿子的dp值加上剩余儿子的数量（必须要结束）。为啥要这样。而不是加上所有呢。

因为我们需要过渡，如果加上所有，那么是不能够让相邻的都保障押韵的。每一个字符串仅有一次机会使用。

可以自行画一下图，举一下例子，体会一下。

#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
int n,cnt = 1,color[1000005],ans;
int tree[1000005][26],dp[1000005];
char s[1000005];
void insert(char *s){//字典树int p = 0;int len = strlen(s + 1);for (int i = len;i >= 1;i --){int z = s[i] - 'a';if (!tree[p][z])tree[p][z] = ++ cnt;p = tree[p][z];}color[p] ++;
}
void dfs(int step){int tot = 0,max1 = 0,max2 = 0;if (color[step])dp[step] ++;for (int i = 0;i <= 25;i ++){//枚举int p = tree[step][i];if (p){dfs(p);if (dp[p] > max1){//最大max2 = max(max2,max1);max1 = dp[p];}else if (dp[p] > max2)//次大max2 = dp[p];tot +=color[p];//是结束了的子节点}}if (!color[step])//本身不结束，卵用没有dp[step] = 0;else dp[step] = max1 + max(1,tot);//最长单链，保证回溯无误ans = max(ans,max1 + max2 + color[step] + max(0,tot - 2));
}int main(){scanf ("%d",&n);for (int i = 1;i <= n;i ++){scanf ("%s",s + 1);insert(s);}dfs(0);printf("%d\n",ans);
}