[SCOI2016]背单词 题解
题目地址:洛谷:【P3294】[SCOI2016]背单词 – 洛谷、BZOJ:Problem 4567. — [Scoi2016]背单词
题目描述
Lweb 面对如山的英语单词,陷入了深深的沉思,”我怎么样才能快点学完,然后去玩三国杀呢?“。这时候睿智的凤老师从远处飘来,他送给了 Lweb 一本计划册和一大缸泡椒,他的计划册是长这样的:
—————序号 单词—————
1 XXX
2 XXX
……
n-2 XXX
n-1 XXX
n XXX
———————————————
然后凤老师告诉 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:
2
题解
如何处理字符串
把字符串翻转一下后缀问题就变成前缀问题了。前缀问题可以用Trie树处理。直接把这些字符串扔进Trie里就好。
贪心
第一种情况明显是最差的。我们可以让这个单词的所有后缀放在它前面来避免这种情况的发生,所以不需要管第一种情况。
第二种情况只会在它没有后缀的情况发生。
第三种情况考虑一种贪心想法,在Trie树上,一个结点的子树为以这个结点为前缀的字符串,统计子树中字符串的数量size,并求出一种DFS序,使得子树小的儿子优先被访问。这样,子树大的儿子中的字符串对答案的贡献将会整体减小。而DFS序保证了前缀都在这个字符串以前。
统计答案
考虑对Trie树简化建树,将不是字符串结尾的结点全部删去,并对新树DFS。每一个儿子对答案的贡献为儿子的DFS序号-父亲的DFS序号。这个可以用当前DFS序号维护一下。写树形DP大概也是可以的?
代码
// Code by KSkun, 2018/2
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
typedef long long LL;
std::vector<int> gra[510005];
int tot1 = 1, siz[510005], dp[510005];
int ch[510005][26], tot = 1;
bool wrd[510005];
int n;
LL pts = 0, ans = 0;
char str[510005];
inline bool cmp(int a, int b) {
return siz[a] < siz[b];
}
inline void insert(char* str) {
int t = 1;
int len = strlen(str);
for(int i = len - 1; i >= 0; i--) {
if(!ch[t][str[i] - 'a']) {
t = ch[t][str[i] - 'a'] = ++tot;
} else {
t = ch[t][str[i] - 'a'];
}
}
wrd[t] = true;
}
inline void rebuild(int fa, int u) {
if(wrd[u]) {
gra[fa].push_back(++tot1);
siz[fa = tot1] = 1;
}
for(int i = 0; i < 26; i++) {
if(ch[u][i]) {
rebuild(fa, ch[u][i]);
}
}
}
inline void calsize(int u) {
for(int i = 0; i < gra[u].size(); i++) {
calsize(gra[u][i]);
siz[u] += siz[gra[u][i]];
}
std::sort(gra[u].begin(), gra[u].end(), cmp);
}
inline void dfs(int u, int w) {
pts++;
ans += pts - w;
w = pts;
if(wrd[u]) dp[u] = 1;
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i];
dfs(v, w);
}
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%s", str);
insert(str);
}
rebuild(1, 1);
calsize(1);
dfs(1, 1);
printf("%lld", ans);
return 0;
}