[Scoi2016]背单词（trie+贪心）

拼搏现实的明天。 2021-11-01 08:44 320阅读 0赞

题意：重新解释一下题意吧（题意晦涩难懂）

给定n个单词，你可以按照顺序学习，当学习这一单词时，这个单词是第x个要学习的单词，需要的代价分三类：

1、若存在其他单词是其后缀没被学习，则代价为n2

2、若不存在其他单词是其后缀，则代价是x

3、否则代价是x-y（y是最靠后的是其后缀的单词学习的位置）

题解：

首先第一种情况要是存在显然不是最优的，然后很容易联想到建立字符串的反串。为了使答案尽可能小，一定存在一种方案为树上的dfs序，容易证明这样一定比不是dfs序更优。然后取出关键点，按照子树大小从小到大排列一下就完了，为什么从小到大排序，因为排队接水问题大家应该是知道的。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int N=5e5+7;
    int n,tot,ch[N][26],val[N],sz[N],dfn[N];
    long long ans;
    char str[N];
    vector<int>G[N];
    void build()
    {
        int len=strlen(str),u=1,c;
        for(int i=len-1;~i;i--)
        {
            c=str[i]-'a';
            if(!ch[u][c])ch[u][c]=++tot;
            u=ch[u][c];
        }
        val[u]=1;
    }
    void dfs1(int u,int fa)
    {
        if(val[u])G[fa].push_back(u);
        for(int i=0;i<26;i++)if(ch[u][i])dfs1(ch[u][i],val[u]?u:fa);
    }
    bool cmp(int a,int b){
         return sz[a]<sz[b];}
    void dfs2(int u,int fa)
    {
        dfn[u]=++tot;
        if(u!=1)ans+=dfn[u]-dfn[fa];
        sort(G[u].begin(),G[u].end(),cmp);
        for(int i=0;i<G[u].size();i++)dfs2(G[u][i],u);
    }
    int main()
    {
        scanf("%d",&n),tot=1;
        for(int i=1;i<=n;i++)scanf("%s",str),build();
        dfs1(1,1);
        for(int i=tot;i;i--)
        if(val[i])
        {
            sz[i]=1;
            for(int j=0;j<G[i].size();j++)sz[i]+=sz[G[i][j]];
        }
        tot=0;
        dfs2(1,0);
        printf("%lld",ans);
    }

转载于:https://www.cnblogs.com/hfctf0210/p/10978014.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/e5f1304d8fa2470886f50aa51bd5b78d.png