[SCOI2016]背单词

题目大意：
　　给你n个字符串，不同的排列有不同的代价，代价按照如下方式计算（字符串s的位置为x）：
　　1.排在s后面的字符串有s的后缀，则代价为n^2；
　　2.排在s前面的字符串有s的后缀，且没有排在s后面的s的后缀，则代价为x-y（y为最后一个与s不相等的后缀的位置）；
　　3.s没有后缀，则代价为x。
　　求最小代价和。

思路：
　　很显然，将这些字符串倒过来后，所有的后缀都变成了前缀，而处理前缀问题的好工具是Trie，因此我们可以考虑将这些字符串倒过来建立一棵Trie。
　　分析不同情况下的代价，很显然，在1的情况下，得到的代价比其他的都大，容易证明在1的情况下，将这个后缀移到s的前面，代价总会比原来小。
　　所以我们不能让情况1出现。
　　考虑一个贪心。
　　只考虑那些为字符串结尾字符的结点，我们要保证每个结点的编号减去其父亲结点编号的和最小。
　　这样从小到大遍历每个结点的子树，得到每个结点的编号即可。

 1 #include<cstdio>
 2 #include<vector>
 3 #include<cstring>
 4 #include<algorithm>
 5 const int N=100001;
 6 const int LEN=510001;
 7 char s[LEN];
 8 std::vector<int> e[N];
 9 int size[N];
10 long long f[N];
11 bool cmp(const int &x,const int &y) {
12     return size[x]<size[y];
13 }
14 class Trie {
15     private:
16         static const int MAX_NODE=LEN;
17         static const int SIGMA_SIZE=26;
18         struct Node {
19             Node *ch[SIGMA_SIZE];
20             int val;
21             Node() {
22                 memset(ch,0,sizeof ch);
23                 val=0;
24             }
25         };
26         int idx(const char &ch) {
27             return ch-'a';
28         }
29     public:
30         Node *root;
31         Trie() {
32             root=new Node;
33         }
34         void insert(char s[],const int &id) {
35             Node *p=root;
36             for(unsigned i=strlen(s)-1;~i;i--) {
37                 int w=idx(s[i]);
38                 if(p->ch[w]) {
39                     p=p->ch[w];
40                 } else {
41                     p=p->ch[w]=new Node;
42                 }
43             }
44             p->val=id;
45         }
46         void rebuild(const Node *x,const int &p) {
47             if(x->val) {
48                 e[p].push_back(x->val);
49             }
50             for(unsigned i=0;i<SIGMA_SIZE;i++) {
51                 Node *y=x->ch[i];
52                 if(!y) continue;
53                 rebuild(y,x->val?x->val:p);
54             }
55             delete x;
56         }
57         void getsize(const int &x) {
58             size[x]=1;
59             for(unsigned i=0;i<e[x].size();i++) {
60                 int &y=e[x][i];
61                 getsize(y);
62                 size[x]+=size[y];
63             }
64             std::sort(e[x].begin(),e[x].end(),cmp);
65         }
66         void solve(const int &x) {
67             f[x]=1;
68             long long tmp=0;
69             for(unsigned i=0;i<e[x].size();i++) {
70                 int &y=e[x][i];
71                 solve(y);
72                 f[x]+=f[y]+tmp;
73                 tmp+=size[y];
74             }
75         }
76 };
77 Trie t;
78 int main() {
79     int n;
80     scanf("%d",&n);
81     for(int i=1;i<=n;i++) {
82         scanf("%s",s);
83         t.insert(s,i);
84     }
85     t.rebuild(t.root,0);
86     t.getsize(0);
87     t.solve(0);
88     printf("%lld
",f[0]-1);
89     return 0;
90 }