題目鏈接: https://www.lydsy.com/JudgeOnline/problem.php?id=4567

題解: 顯然答案一定小于\(n\times n\), 字符串倒過來變成前綴建Trie, 題意轉化如下:

每次可以在一棵樹上標記一個點，要求標記一個點之前所有祖先都標記過，標記一個點的價值等于它父親被標記的時間，最大化價值和(也可以是求所有父子標記時間之差的和的最小值)

一看到這個腦子里立刻蹦出一個貪心: 按照兒子個數(shù)從小到大選(用堆維護)

然而是錯的

hack數(shù)據(jù):

10 aaa baa caa daa eaa aa a b ab bb

正確的方案是按子樹大小從小到大選。這里提供一個不知道對不對的證明(其實是拼湊網(wǎng)上的其他題解):

(1) 最優(yōu)答案一定是DFS序。這個按照父子時間差之和來理解，挺顯然。(抱歉我水平有限也就能說到這個份上了……)

(2) DFS序中的最優(yōu)答案一定是按子樹大小從小到大選。感性理解是: 由于是DFS序我們可以只考慮根對答案產生的貢獻，最小化根與其所有兒子的時間差之和。然后就相當于有一堆數(shù)給他們排序使得前綴和的和最小，然后就顯然了……

教訓: 貪心這種東西千萬不能想當然，一定要證明！要證明！要證明！

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<queue> #define llong long long using namespace std;const int N = 1e5; const int L = 5e5+1e4; const int S = 26; struct Edge {int v,nxt; } e[(N<<1)+3]; int son[L+3][S+1]; char str[L+3]; bool isky[L+3]; int sz[N+3]; int sonn[N+3]; int fe[N+3]; int fa[N+3]; struct Element {int u;Element() {}Element(int _u) {u = _u;}bool operator <(const Element &arg) const{return sz[u]>sz[arg.u];} }; priority_queue<Element> que; int n,siz,nn,en;void insertstr(char str[],int len) {int u = 1;for(int i=1; i<=len; i++){if(!son[u][str[i]]) {siz++; son[u][str[i]] = siz;}u = son[u][str[i]];}isky[u] = true; }void addedge(int u,int v) {printf("addedge %d %d\n",u,v);en++; e[en].v = v;e[en].nxt = fe[u]; fe[u] = en; }void dfs0(int u,int anc) {if(isky[u]) {nn++; addedge(nn,anc); addedge(anc,nn); sonn[anc]++; anc = nn;}for(int i=1; i<=S; i++){int v = son[u][i];if(v){dfs0(v,anc);}} }void dfs(int u) {sz[u] = 1;for(int i=fe[u]; i; i=e[i].nxt){if(e[i].v==fa[u]) continue;fa[e[i].v] = u;dfs(e[i].v);sz[u] += sz[e[i].v];} }int main() {siz = 1;scanf("%d",&n);for(int i=1; i<=n; i++){scanf("%s",str+1); int len = strlen(str+1);for(int j=1; j<=len; j++) str[j] -= 96;for(int j=1; j<=len+1-j; j++) swap(str[j],str[len+1-j]);insertstr(str,len);}nn = 1; dfs0(1,1);dfs(1);que.push(Element(1));llong ans = 0ll;for(int i=1; i<=nn; i++){int u = que.top().u; que.pop();printf("%d\n",u);ans += sonn[u]*(i-1ll);for(int j=fe[u]; j; j=e[j].nxt){if(e[j].v==fa[u]) continue;fa[e[j].v] = u;que.push(e[j].v);}}ans = n*(n+1ll)/2ll-ans;printf("%lld\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的BZOJ 4567 [SCOI2016]背单词 (Trie树、贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。