[2018.12.6]BZOJ2809 [Apio2012]dispatching

柔光的暖阳◎ 2021-12-23 22:35 216阅读 0赞

考虑维护每一个点以及它的子树中被派遣的忍者。

对于一个点,我们用类似树形DP的方式自底向上进行,先把它的所有孩子中被派遣的忍者放到一起,如果他们的薪水总和超过\\(m\\),就不停地将其中薪水最大的忍者删除,直到薪水总和小于等于\\(m\\)。

找到所有点中领导能力和被派遣忍者数量乘积的最大值即可。

即维护数据结构,支持合并,删除和求最大值。

就是维护可并堆。

可以使用左偏树。

[左偏树][Link 1]

#include<bits/stdc++.h> using namespace std; struct Ltree{ int v,d,f,c[2]; }t[100010]; int n,m,b[100010],c[100010],l[100010],f[100010]; long long ans,num[100010],sum[100010]; vector<int>e[100010]; int Merge(int &x,int &y){ if(!y)return x; if(!x){ swap(x,y); return x; } if(t[x].v<t[y].v)swap(x,y); Merge(t[x].c[1],y); t[t[x].c[1]].f=x; if(t[t[x].c[0]].d<t[t[x].c[1]].d)swap(t[x].c[0],t[x].c[1]); t[x].d=t[t[x].c[1]].d+1; return x; } int Delete(int x){ t[t[x].c[0]].f=t[t[x].c[1]].f=0; return Merge(t[x].c[0],t[x].c[1]); } void TDP(int x){ for(int i=0;i<e[x].size();i++){ if(e[x][i]!=b[x]){ TDP(e[x][i]); if(f[e[x][i]]){ num[x]+=num[e[x][i]]; sum[x]+=sum[e[x][i]]; f[x]=Merge(f[x],f[e[x][i]]); } } } while(sum[x]>m){ sum[x]-=t[f[x]].v; num[x]--; f[x]=Delete(f[x]); } ans=max(ans,num[x]*l[x]); } int main(){ scanf("%d%d",&n,&m); t[0].d=-1; for(int i=1;i<=n;i++){ scanf("%d%d%d",&b[i],&c[i],&l[i]); f[i]=i; e[b[i]].push_back(i); t[i].v=c[i]; t[i].d=0; num[i]=1; sum[i]=c[i]; } TDP(1); printf("%lld",ans); return 0; }

转载于:https://www.cnblogs.com/xryjr233/p/BZOJ2809.html

[Link 1]: https://www.cnblogs.com/xryjr233/p/10536872.html

发表评论取消回复

表情：

评论列表（有 0 条评论，216人围观）

还没有评论，来说两句吧...

相关阅读

相关 ❤BZOJ 2705: [SDOI2012]Longge的问题

2705: \[SDOI2012\]Longge的问题 Time Limit: 3 Sec Memory Limit: 128 MB Submit: 2007 Sol

我会带着你远行/ 2022年07月29日 08:59/ 0 赞/ 147 阅读

相关 Flux Dispatch.dispatch(…): Cannot dispatch in the middle of a dispatch

在使用flux进行数据交互的时候，出现了一个问题`Flux Dispatch.dispatch(…): Cannot dispatch in the middle of a d

忘是亡心i/ 2022年05月30日 03:09/ 0 赞/ 289 阅读

相关 BZOJ3012 : [Usaco2012 Dec]First!

建立Trie，那么成为答案的串必须满足其终止节点到根路径上没有其它点。对于Trie上每个节点维护一个bitset，表示哪些字符必须在哪些字符之前。每到达一个可能成为答案

深碍√TFBOYSˉ_/ 2022年04月10日 11:24/ 0 赞/ 171 阅读

相关 [APIO2013]道路费用

[\[APIO2013\]道路费用 ][APIO2013] 给一些边确定权值，再找MST，还要最大化，很麻烦不妨枚举k中一个子集最终会在MST上，此基础上最大化每个边的权

我不是女神ヾ/ 2022年01月12日 10:47/ 0 赞/ 244 阅读

相关 [2018.12.6]BZOJ2809 [Apio2012]dispatching

考虑维护每一个点以及它的子树中被派遣的忍者。对于一个点,我们用类似树形DP的方式自底向上进行,先把它的所有孩子中被派遣的忍者放到一起,如果他们的薪水总和超过\\(m\\),

川长思鸟来/ 2022年01月09日 05:37/ 0 赞/ 180 阅读

相关 [2018.12.6]BZOJ2809 [Apio2012]dispatching

考虑维护每一个点以及它的子树中被派遣的忍者。对于一个点,我们用类似树形DP的方式自底向上进行,先把它的所有孩子中被派遣的忍者放到一起,如果他们的薪水总和超过\\(m\\),

柔光的暖阳◎/ 2021年12月23日 22:35/ 0 赞/ 217 阅读

相关 APIO2019

device：用最小公倍数的知识或是画网格模拟转移，神仙们也可以找规律。然后就变成区间覆盖了。忘记特殊情况了，大众分→Ag include<iostream>

深藏阁楼爱情的钟/ 2021年11月22日 07:00/ 0 赞/ 232 阅读

相关 [Apio2012]dispatching（派遣）——线段树合并

题面　　[Bzoj2809][] 解析　　按照贪心策略我们想选尽量多的人，所以就会选费用少的人，那么对于每个节点可以建一棵值域线段树，父亲的线段树由他的所有儿子的线段

桃扇骨/ 2021年11月22日 05:16/ 0 赞/ 311 阅读

相关 P3629 【[APIO2010]巡逻】

今天在机房里考了这题。。。。。lbw巨佬一下考场就开始大喊“第二题把直径赋为-1再跑一次直径就行”，作为一个蒟蒻也没有啥好说的，自己弱，没办法。下午再想这道题，忽然有个暴力的

叁歲伎倆/ 2021年11月17日 21:54/ 0 赞/ 219 阅读

相关 bzoj2753: [SCOI2012]滑雪与时间胶囊

这题真的很容易想到最小生成树。而且题目有特别的性质，高处的连低处的是单向的，但是不会构环（老实讲一开始就是担心这个，但是现在发现好像没啥影响吧），所以其实先把能够访问的点d

水深无声/ 2021年09月29日 16:48/ 0 赞/ 247 阅读