这是一道贪心题
刚开始yy出来一个比较(sb)的贪心
之后发现它错了
首先这道题得先把题面翻译成人话
-
如果存在一个单词是它的后缀，且当前没被填入，代价为(n*n)；
-
如果不存在一个单词是它的后缀，代价为(x)；
-
如果存在一个单词是它的后缀，且已填入的是它后缀的单词中序号最大的为(y)，代价为(x-y)。
显然如果出现了第一种情况那肯定就凉了，这个花费太大了
显然这是可以避免的，我们在插入一个串之前就必须把它的所有后缀插入
所以这里就需要(Trie)树了，我们将所有的串倒着插入(Trie)树，之后(Trie)树就可以处理后缀了
那之后呢，我们在原来的(Trie)上贪心吗
不是的，我们应该在建立一个新图，在这个图上我们用一个点代表一个字符串，每个点的父亲是他的后缀
于是我们就得到了一棵新的树
之后贪心就好了，优先选择子树较小的
这是非常显然的
首先我们明确一点，就是一个子树内部的相对答案是不会变的，就是说在这个子树内部被选择的第一个点被选择的顺序是(x)，那么答案一定会是(x+val)，(val)是固定的一个数，也就是这个子树内部的最优策略
所以我们要尽量保证进入每一棵子树的(x)的和尽量的小，显然我们优先选择较小的可以做到这一点
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<bitset>
#define re register
#define mp std::make_pair
#define maxn 510005
struct E
{
int v,nxt;
}e[maxn<<1];
char S[maxn];
int n,cnt,tot;
long long ans;
std::bitset<maxn> f;
int son[maxn][26];
int sz[maxn];
int num,head[maxn],sum[maxn];
typedef std::pair<int,int> pii;
std::priority_queue<pii,std::vector<pii>,std::greater<pii> > q[maxn];
inline void add_edge(int x,int y)
{
e[++num].v=y;
e[num].nxt=head[x];
head[x]=num;
}
inline void ins()
{
scanf("%s",S+1);
int now=0;
int len=strlen(S+1);
for(re int i=len;i;--i)
{
if(!son[now][S[i]-'a']) son[now][S[i]-'a']=++cnt;
now=son[now][S[i]-'a'];
}
f[now]=1;
}
void build(int x,int pre)
{
for(re int i=0;i<26;i++)
if(son[x][i])
{
if(f[son[x][i]]) add_edge(pre,son[x][i]),build(son[x][i],son[x][i]);
else build(son[x][i],pre);
}
}
void dfs(int x)
{
sum[x]=1;
for(re int i=head[x];i;i=e[i].nxt)
{
dfs(e[i].v);
sum[x]+=sum[e[i].v];
q[x].push(mp(sum[e[i].v],e[i].v));
}
}
void last(int x,int pre)
{
while(!q[x].empty())
{
tot++;
ans+=tot-pre;
int mid=q[x].top().second;
last(mid,tot);
q[x].pop();
}
}
int main()
{
scanf("%d",&n);
for(re int i=1;i<=n;i++) ins();
build(0,0);
dfs(0);
last(0,0);
std::cout<<ans;
return 0;
}