「Luogu1552」[APIO2012]派遣

最近狀態都不是很好，寫完這個題感覺手感好像恢復了一些

---

problem

Solution

這個數據范圍顯然樹形DP是做不了的

我們考慮，在預算范圍內，選中的忍者越多越好，那么我們在一棵子樹中選中的忍者一定是薪水最少的若干個

對每個節點維護一個大根堆，并記錄每個堆的大小和堆中元素的權值和

考慮一棵子樹時，用類似樹形DP的方法將所有兒子合并到根

如果堆中元素權值和大于預算，不斷彈出堆頂直到權值和不大于預算即可

最后對子樹進行統計，更新答案

可并堆可以用左偏樹實現

另外，還需要記錄每個節點對應的左偏樹的根的編號

Code

一開始沒開long long還wa了一發

#include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <cstring> #include <iostream> #include <queue> using namespace std; typedef long long ll;template <typename T>void read(T &t) {t=0;int f=0;char c=getchar();while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){t=t*10+c-'0';c=getchar();}if(f)t=-t; }const int maxn=100000+5; int n,root; ll m; ll mng[maxn]; ll ans;struct edge {int u,v,nxt; }g[maxn];int head[maxn],ecnt; void eADD(int u,int v) {g[++ecnt].u=u;g[ecnt].v=v;g[ecnt].nxt=head[u];head[u]=ecnt; }int rec[maxn]; struct node {int ls,rs,dist;ll val,siz,sum; }mxh[maxn];int Merge(int x,int y) {if(!x || !y)return x+y;if(mxh[x].val<mxh[y].val)swap(x,y);mxh[x].rs=Merge(mxh[x].rs,y);if(mxh[mxh[x].ls].dist<mxh[mxh[x].rs].dist)swap(mxh[x].ls,mxh[x].rs);mxh[x].dist=mxh[mxh[x].rs].dist+1;mxh[x].siz=mxh[mxh[x].ls].siz+mxh[mxh[x].rs].siz+1;mxh[x].sum=mxh[mxh[x].ls].sum+mxh[mxh[x].rs].sum+mxh[x].val;return x; }int Pop(int x) {int ls=mxh[x].ls,rs=mxh[x].rs;return Merge(ls,rs); }void dfs(int u) {for(register int i=head[u];i;i=g[i].nxt){int v=g[i].v;dfs(v);rec[u]=Merge(rec[u],rec[v]);}while(mxh[rec[u]].sum>m && mxh[rec[u]].siz)rec[u]=Pop(rec[u]);ans=max(ans,1ll*mxh[rec[u]].siz*mng[u]); }int main() {read(n),read(m);for(register int i=1;i<=n;++i){int u;read(u),read(mxh[i].val),read(mng[i]);mxh[i].sum=mxh[i].val;mxh[i].siz=1;rec[i]=i;if(u)eADD(u,i);else root=i;}dfs(root);printf("%lld",ans); return 0; }

轉載于:https://www.cnblogs.com/lizbaka/p/10657928.html

總結

以上是生活随笔為你收集整理的「Luogu1552」[APIO2012]派遣的全部內容，希望文章能夠幫你解決所遇到的問題。

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