宿州做企业网站公司,中国建设人才网官网登录入口2022,网站建设明细费用,美术设计与制作由于题目涉及到后缀#xff0c;不难想到用 trie 树处理。
将每个字符串翻转插入 trie#xff0c;后缀就变成了前缀#xff0c;方便处理。
条件 LCS ( A , B ) ≥ max ( ∣ A ∣ , ∣ B ∣ ) − 1 \text{LCS}(A,B) \ge \max(|A|,|B|)-1 LCS(A,B)≥max(∣A∣,∣B∣)−1不难想到用 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 szix∈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-1val_i fix∈sonxmax(fx)szi−1vali。
如果 v a l i 0 val_i0 vali0说明都没有字符串 f i 0 f_i0 fi0。
更新答案时记录儿子 f s o n i f_{son_i} fsoni 的最大和次大再加上剩余儿子和自己的 v a l val val。感性理解一条链只有两个位置是“自由”的由此设出 DP 状态
本题卡空间所以建 trie 树时要动态开点。
具体实现参见代码。
#includebits/stdc.h
using namespace std;
const int N3e610;
int cnt1,n,f[N],ans;
char a[N];
struct node
{vectorpairint,int son;int fa,val;
}tr[N];
void insert(int rt,char a[],int len)
{for(int i0;ilen;i){int xa[i]-97;for(auto j:tr[rt].son){if(j.firstx){rtj.second;goto a;}}tr[rt].son.push_back(make_pair(x,cnt));rttr[rt].son.back().second;a:;}tr[rt].val;
}
void dfs(int rt)
{int aa0,bb0,x0,y0,sum0;for(auto i:tr[rt].son){dfs(i.second);sumtr[i.second].val;f[rt]max(f[rt],f[i.second]);if(f[i.second]aa){bbaa;aaf[i.second];yx;xtr[i.second].val;}else if(f[i.second]bb) bbf[i.second],ytr[i.second].val;}f[rt]sum-x;if(!tr[rt].son.size()) ansmax(ans,tr[rt].val);else ansmax(ans,aabb-x-ysumtr[rt].val);if(!tr[rt].val) f[rt]0;else f[rt];
}
int main()
{scanf(%d,n);for(int i1;in;i){scanf(%s,a);int lenstrlen(a);reverse(a,alen);insert(1,a,len);}dfs(1);coutans;
}
