[luogu] P3294 [SCOI2016]背单词（贪心）

题目描述

Lweb 面对如山的英语单词，陷入了深深的沉思，”我怎么样才能快点学完，然后去玩三国杀呢？“。这时候睿智的凤老师从远处飘来，他送给了 Lweb 一本计划册和一大缸泡椒，他的计划册是长这样的：

—————序号单词—————

1 2......n-2n-1 n—————

然后凤老师告诉 Lweb ，我知道你要学习的单词总共有 n 个，现在我们从上往下完成计划表，对于一个序号为 x 的单词（序号 1...x-1 都已经被填入）：

如果存在一个单词是它的后缀，并且当前没有被填入表内，那他需要吃 n*n 颗泡椒才能学会；
当它的所有后缀都被填入表内的情况下，如果在 1...x-1 的位置上的单词都不是它的后缀，那么你吃 x 颗泡椒就能记住它；
当它的所有后缀都被填入表内的情况下，如果 1...x-1的位置上存在是它后缀的单词，所有是它后缀的单词中，序号最大为 y ，那么你只要吃 x-y 颗泡椒就能把它记住。

Lweb 是一个吃到辣辣的东西会暴走的奇怪小朋友，所以请你帮助 Lweb ，寻找一种最优的填写单词方案，使得他记住这 n 个单词的情况下，吃最少的泡椒。

输入输出格式

输入格式：

输入一个整数 n ，表示 Lweb 要学习的单词数。

接下来 n 行，每行有一个单词（由小写字母构成，且保证任意单词两两互不相同）1<=n<=100000, 所有字符的长度总和 1<=|len|<=510000

输出格式：

Lweb 吃的最少泡椒数

输入输出样例

输入样例#1： 复制

2

a

ba

输出样例#1： 复制

题解

选择1.告诉你选了就一定不是最优的。

选择2.告诉你如果当前的单词没有后缀，那么你加入它的代价为x。

选择3.告诉你如果当前的单词有后缀，那么你加入它的代价为x-y，y为最接近x的当前单词的后缀的序号。

本题意就是告诉你。

其实3个选择相当于一个选择，1选不了，2和3等价。因为2操作的y=0。

题意就转化为了接水问题。

假如n个人，分别需要\(a_i\)的时间。我们肯定优先从小到大接水。

这样所有人等待的时间最少。

现在问题转化到了一棵树上，就优先跑子树最小的即可。

Ps：我们可以把后缀转化为前缀建字典树，然后转化成一颗正常的树。

Code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<iostream>

#include<queue>

using namespace std;

const int N=1e6+5;

int tot,num,idx,n,head[N],size[N];

long long ans=0;

struct node{

	int to,nex;

}e[N<<1];

struct tree{

	int ch[26],end;

}t[N<<1];

char s[N];

void add(int from,int to){

	num++;

	e[num].to=to;

	e[num].nex=head[from];

	head[from]=num;

}

void build(){

	int l=strlen(s+1),now=0;

	for(int i=l;i>=1;i--){

		int j=s[i]-'a';

		if(!t[now].ch[j])

		t[now].ch[j]=++tot;

		now=t[now].ch[j];

	}t[now].end=1;

}

void init(int x,int ff){

	for(int i=0;i<26;i++){

		if(t[x].ch[i]){

			if(t[t[x].ch[i]].end){

				add(ff,t[x].ch[i]);

				init(t[x].ch[i],t[x].ch[i]);

			}

			else init(t[x].ch[i],ff);

		}

	}

}

void prep(int x,int ff){

	size[x]=1;

	for(int i=head[x];i;i=e[i].nex){

		int v=e[i].to;

		if(v==ff)continue;

		prep(v,x);size[x]+=size[v];

	}

}

void dfs(int x,int y){

	priority_queue<pair<int,int> >q;

	idx++;  ans+=1ll*(idx-y);int tmp=idx;

	for(int i=head[x];i;i=e[i].nex){

		int v=e[i].to;

		q.push(make_pair(-size[v],v));

	}

	while(q.size()){dfs(q.top().second,tmp);q.pop();}

}

int main(){

	cin>>n;

	for(int i=1;i<=n;i++)

		scanf("%s",s+1),build();

	init(0,0);

	prep(0,0);

	dfs(0,0);

	cout<<ans-1<<endl;

	return 0;

}

巴特西

[luogu] P3294 [SCOI2016]背单词（贪心）

题目描述

输入输出格式

输入输出样例

题解

Code

最新文章

热门文章

巴特西

[luogu] P3294 [SCOI2016]背单词 （贪心）

题目描述

输入输出格式

输入输出样例

题解

Code

最新文章

热门文章

[luogu] P3294 [SCOI2016]背单词（贪心）