[2018.12.6]BZOJ2809 [Apio2012]dispatching

柔光的暖阳◎ 2021-12-23 22:35 231阅读 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 条评论，231人围观）

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

相关阅读

相关 dispatch(dispatched)

英语单词distribute和dispatch意义上有什么区别? 可以互换,distribute强调的是向众多的对象发送众多的东西，dispatch主要的对象是信件，包裹

绝地灬酷狼/ 2023年09月26日 12:06/ 0 赞/ 69 阅读

相关 @bzoj - 2668@ [cqoi2012]交换棋子

目录 @description@ @solution@ @accepted code@ @details@ --------------------

Love The Way You Lie/ 2023年06月01日 14:56/ 0 赞/ 12 阅读

相关【左偏树】[APIO2012]派遣

题意可真的是有毒第一眼树形背包可做？（反正我没用树形背包打过，边上巨佬打的背包似乎没拿分）后来发现可以贪心搞，我们先把一个节点所有的儿子都取进去，之后不行的话再从大的开

刺骨的言语ヽ痛彻心扉/ 2023年06月01日 06:08/ 0 赞/ 8 阅读

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

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

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

相关 BZOJ3012 : [Usaco2012 Dec]First!

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

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

相关 [2018.12.6]BZOJ2809 [Apio2012]dispatching

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

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

相关 [2018.12.6]BZOJ2809 [Apio2012]dispatching

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

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

相关 APIO2019

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

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

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

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

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

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

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

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