【BZOJ4567】[Scoi2016]背单词

Description

Lweb 面对如山的英语单词，陷入了深深的沉思，“我怎么样才能快点学完，然后去玩三国杀呢？”。这时候睿智

的凤老师从远处飘来，他送给了 Lweb 一本计划册和一大缸泡椒，他的计划册是长这样的：

—————

序号单词

—————

……

n-2

n-1

—————

然后凤老师告诉 Lweb ，我知道你要学习的单词总共有 n 个，现在我们从上往下完成计划表，对于一个序号为 x

的单词（序号 1...x-1 都已经被填入）：

1) 如果存在一个单词是它的后缀，并且当前没有被填入表内，那他需要吃 n×n 颗泡椒才能学会；

2) 当它的所有后缀都被填入表内的情况下，如果在 1...x-1 的位置上的单词都不是它的后缀，那么你吃 x 颗泡

椒就能记住它；

3) 当它的所有后缀都被填入表内的情况下，如果 1...x-1的位置上存在是它后缀的单词，所有是它后缀的单词中

，序号最大为 y ，那么你只要吃 x-y 颗泡椒就能把它记住。

Lweb 是一个吃到辣辣的东西会暴走的奇怪小朋友，所以请你帮助 Lweb ，寻找一种最优的填写单词方案，使得他

记住这 n 个单词的情况下，吃最少的泡椒。

Input

输入一个整数 n ，表示 Lweb 要学习的单词数。接下来 n 行，每行有一个单词（由小写字母构成，且保证任意单

词两两互不相同）1≤n≤100000, 所有字符的长度总和 1≤|len|≤510000

Output

Lweb 吃的最少泡椒数

Sample Input

2
a
ba

Sample Output

题解：我们将单词倒序扔到Trie树中去，然后根据贪心可知如果想填入一个单词，那么它父亲节点上的单词一定已经被填入，现在的问题就是我们如何处理一个父亲的多个儿子的填入顺序。

又根据贪心可知，如果一个单词有多个儿子，那么一定先走子树最小的那个儿子，这是可证明的，但我懒啊~

#include <cstdio>#include <cstring>#include <iostream>#include <queue>#include <algorithm>using namespace std;int n,tot,cnt,now;long long ans;const int maxn=100010;struct node{	int ch[26],v,sm,from;}p[500010];char str[500010];int fa[maxn],next[maxn],head[maxn],to[maxn],pos[maxn],q[maxn],siz[maxn],s[maxn],Q[maxn];void add(int a,int b){	to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;}void dfs1(int x){	siz[x]=1;	for(int i=head[x];i!=-1;i=next[i])	dfs1(to[i]),siz[x]+=siz[to[i]];}bool cmp(int a,int b){	return siz[a]<siz[b];}void dfs2(int x){	int i,sum=0;	ans+=s[x]-s[fa[x]];	for(i=head[x];i!=-1;i=next[i])	q[++sum]=to[i];	sort(q+1,q+sum+1,cmp);	for(sum=0,i=head[x];i!=-1;i=next[i])	to[i]=q[++sum];	for(i=head[x];i!=-1;i=next[i])	s[to[i]]=++now,dfs2(to[i]);}int main(){	scanf("%d",&n);	int i,j,a,b,u;	tot=1;	for(i=1;i<=n;i++)	{		scanf("%s",str);		a=strlen(str);		for(u=1,j=a-1;j>=0;j--)		{			b=str[j]-‘a‘;			if(!p[u].ch[b])	p[u].ch[b]=++tot,p[p[u].ch[b]].from=u;			u=p[u].ch[b];		}		p[u].v=i,pos[i]=u;;	}	memset(head,-1,sizeof(head));	for(i=1;i<=n;i++)	{		u=p[pos[i]].from;		while(u!=1&&!p[u].v)	u=p[u].from;		fa[i]=p[u].v,add(fa[i],i);	}	dfs1(0),dfs2(0);	printf("%lld",ans);	return 0;}

【BZOJ4567】[Scoi2016]背单词 Trie树+贪心

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 【BZOJ4567】[Scoi2016]背单词 Trie树+贪心