bzoj4567 [Scoi2016]背单词

Lweb 面对如山的英语单词，陷入了深深的沉思，“我怎么样才能快点学完，然后去玩三国杀呢？”。这时候睿智

的凤老师从远处飘来，他送给了 Lweb 一本计划册和一大缸泡椒，他的计划册是长这样的：

—————

序号单词

—————

……

n-2

n-1

—————

然后凤老师告诉 Lweb ，我知道你要学习的单词总共有 n 个，现在我们从上往下完成计划表，对于一个序号为 x

的单词（序号 1...x-1 都已经被填入）：

1) 如果存在一个单词是它的后缀，并且当前没有被填入表内，那他需要吃 n×n 颗泡椒才能学会；

2) 当它的所有后缀都被填入表内的情况下，如果在 1...x-1 的位置上的单词都不是它的后缀，那么你吃 x 颗泡

椒就能记住它；

3) 当它的所有后缀都被填入表内的情况下，如果 1...x-1的位置上存在是它后缀的单词，所有是它后缀的单词中

，序号最大为 y ，那么你只要吃 x-y 颗泡椒就能把它记住。

Lweb 是一个吃到辣辣的东西会暴走的奇怪小朋友，所以请你帮助 Lweb ，寻找一种最优的填写单词方案，使得他

记住这 n 个单词的情况下，吃最少的泡椒。

Input

输入一个整数 n ，表示 Lweb 要学习的单词数。接下来 n 行，每行有一个单词（由小写字母构成，且保证任意单

词两两互不相同）1≤n≤100000, 所有字符的长度总和 1≤|len|≤510000

Output

Lweb 吃的最少泡椒数

Sample Input

2 
a 
ba

Sample Output

2

题解：
　　　题目是可以贪心的，刚开始的时候想抄发题解，发现风格不同，算了，自己打吧。
　　　　然后自己瞎搞了半天，首先，n*n的那个是绝对不可以直接选的，这个选了，那是
　　　　要爆炸的，然后考虑两种，应该后缀先加入，这个方向思考，可以发现，应该可以
　　　　转化为图论，应该是最短后缀先背，然后次短，...，到达该单词为止。
　　　　这里可以用字典树预处理出来，就是构建图出来，变成了多个联通块，这时该怎么办
　　　　发现，这是多个DAG，就是拓扑图，然后建立一个虚根，来连接这些点。

　　　　　　很明显右边那种不行，不可能两种长度一样的后缀，因为题目保证给定单词两两不同。

　　　　　　然后就是一棵树了，并且将问题进一步转化，每个点的花费，就是其儿子节点编号减父亲

　　　　　　节点编号，这样怎么样最小，可以证明，每次优先编号size小的子树，这样花费最小。

　　　　　　挺好证明的吧，然后就ok了，dfs一次就好了。

  1 #include<cstring>
  2 #include<iostream>
  3 #include<cmath>
  4 #include<algorithm>
  5 #include<cstdio>
  6 #include<queue>
  7 #include<vector>
  8 #define N 100007
  9 #define LEN 510007
 10 #define fzy pair<int,int>
 11 #define ll long long
 12 using namespace std;
 13 
 14 int n;
 15 int ckt,top=1,bh[N],siz[N],du[N];
 16 ll ans;
 17 int cnt,head[N],next[N],rea[N];
 18 vector<int>ch[N];
 19 char s[LEN];
 20 struct Node
 21 {
 22     int point[26],flag;
 23 }trie[LEN*2];
 24 
 25 void insert(int x)
 26 {
 27     int now=1,len=ch[x].size()-1;
 28     for (int i=len;i>=0;i--)
 29     {
 30         if (!trie[now].point[ch[x][i]])
 31         {
 32             trie[now].point[ch[x][i]]=++top;
 33             now=top;
 34         }
 35         else now=trie[now].point[ch[x][i]];
 36     }
 37     trie[now].flag=x;
 38 }
 39 void add(int u,int v)
 40 {
 41     next[++cnt]=head[u];
 42     head[u]=cnt;
 43     rea[cnt]=v;
 44     du[v]++;
 45 }
 46 void solve_make(int x)
 47 {
 48     int now=1,len=ch[x].size()-1,id=-1;
 49     for (int i=len;i>=0;i--)
 50     {
 51         if (trie[now].flag) id=trie[now].flag;
 52         now=trie[now].point[ch[x][i]];
 53     }
 54     if (id!=-1&&id!=x) add(id,x);
 55 }
 56 void dfs_init(int u,int fa)
 57 {
 58     siz[u]=1;
 59     for (int i=head[u];i!=-1;i=next[i])
 60     {
 61         int v=rea[i];
 62         if (v==fa) continue;
 63         dfs_init(v,u);
 64         siz[u]+=siz[v];
 65     }
 66 }
 67 void dfs_solve(int u,int fa)
 68 {
 69     priority_queue<fzy,vector<fzy>,greater<fzy> >q;
 70     while(!q.empty()) q.pop();
 71     bh[u]=++ckt;
 72     ans+=bh[u]-bh[fa];
 73     for (int i=head[u];i!=-1;i=next[i])
 74     {
 75         int v=rea[i];
 76         if (v==fa) continue;
 77         q.push(make_pair(siz[v],v));
 78     }
 79     while(!q.empty())
 80     {
 81         int now=q.top().second;
 82         dfs_solve(now,u);
 83         q.pop();
 84     }
 85 }
 86 int main()
 87 {
 88     memset(head,-1,sizeof(head));
 89     scanf("%d",&n);
 90     for (int i=1;i<=n;i++)
 91     {
 92         scanf("%s",s);
 93         for (int j=0;j<strlen(s);j++)
 94             ch[i].push_back((int)(s[j]-'a'));
 95         insert(i);
 96     }
 97     for (int i=1;i<=n;i++)
 98         solve_make(i);
 99     int S=n+1;
100     for (int i=1;i<=n;i++)
101         if (du[i]==0) add(S,i);
102     dfs_init(S,S);
103     dfs_solve(S,S);    
104     printf("%lld
",ans);
105 }