4567: [Scoi2016]背单词

https://www.lydsy.com/JudgeOnline/problem.php?id=4567

题意：

　　题意看了好久，最后在其他人的博客里看懂了的。

　　n个字符串，给它们排一个顺序。花费最小。对于第x个位置字符串的花费如下计算是这样的：

如果存在它的一个后缀单词在它的后面，花费为x*x
如果它的所有后缀单词都在它前面了，花费为x-last_pos（last_pos为它的后缀单词最后一个出现的位置，如果没有则为0）。

分析：

　　贪心 + dfs序。

　　首先第一个花费一定是不优的。那就是一个单词在它的所有的后缀单词的后面。

　　然后反着建出trie树。把非单词结尾的节点去掉，然后形成一棵树。现在就是给这棵树编号，花费为所有的Σid[x]-id[fa[x]]。

　　贪心的思路：优先给siz小的子树编号。

　　理解一下：假设现在又两棵子树，第一棵子树的大小为a，另一棵为b，(a<b)。先给a编号后，子树b的根就是a+1，Ans+=(a+b)-id[fa]，先给b编号，子树a的根为b+1，Ans+=(b+1)-id[fa]。然后子树内部的点的花费与父节点的差，所以不论父节点是多少，按照最优的情况编号，不变。

代码：

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<cctype>
 7 #include<set>
 8 #include<vector>
 9 #include<queue>
10 #include<map>
11 #define fi(s) freopen(s,"r",stdin);
12 #define fo(s) freopen(s,"w",stdout);
13 using namespace std;
14 typedef long long LL;
15 
16 inline int read() {
17     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
18     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
19 }
20 
21 const int N = 510001;
22 
23 int ch[N][26], dfn[N], siz[N], val[N], NowTime, Index;
24 char s[N];
25 vector<int> T[N];
26 LL Ans;
27 
28 void Insert(char *s,int n) {
29     int u = 1;
30     for (int i=n; i>=1; --i) {
31         int c = s[i] - 'a';
32         if (!ch[u][c]) ch[u][c] = ++Index;
33         u = ch[u][c];
34     }
35     val[u] = 1;
36 }
37 void build(int u,int fa) {
38     if (val[u]) T[fa].push_back(u);
39     for (int i=0; i<26; ++i) 
40         if (ch[u][i]) build(ch[u][i], val[u] ? u : fa);
41 }
42 bool cmp(int a,int b) {
43     return siz[a] < siz[b];
44 }
45 void dfs(int u,int fa) {
46     dfn[u] = ++NowTime;
47     if (u != 1) Ans += dfn[u] - dfn[fa];
48     sort(T[u].begin(), T[u].end(), cmp);
49     for (int i=0; i<T[u].size(); ++i) dfs(T[u][i], u);
50 }
51 int main() {
52     int n = read();
53     Index = 1;
54     for (int i=1; i<=n; ++i) {
55         scanf("%s",s + 1);
56         Insert(s, strlen(s + 1));
57     }
58     build(1, 1);
59     for (int i=Index; i>=1; --i) {
60         if (!val[i]) continue;
61         siz[i] = 1;
62         for (int j=0; j<T[i].size(); ++j) siz[i] += siz[T[i][j]];
63     }
64     dfs(1, 0);
65     cout << Ans;
66     return 0;
67 }