题目地址：洛谷：【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 都已经被填入）：

1. 如果存在一个单词是它的后缀，并且当前没有被填入表内，那他需要吃 n*n 颗泡椒才能学会；
2. 当它的所有后缀都被填入表内的情况下，如果在 1…x-1 的位置上的单词都不是它的后缀，那么你吃 x 颗泡椒就能记住它；
3. 当它的所有后缀都被填入表内的情况下，如果 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;
}