Steal 偷天换日题解(From luoguBlog)

我就是我 2021-10-29 08:50 152阅读 0赞

树形+背包 奇奇怪怪的dp。

考试的时候费了半天劲把题读完后思路基本正解，

然而也不知道为什么脑子鬼畜了一下打了个非递归建树？

而且链式前向星建边？

岔路口和藏品都搞成节点？

自己给自己找麻烦Orz。

于是输入爆炸，无法调试。

比较简便的打法是把权值左右儿子几个藏品各多少钱都塞到结构体里，一边建树一遍跑dp（在每个馆里跑背包然后把儿子的价值树形dp到根）；

然而还是有很多坑点  
所以恐怖如斯如机房里的各路大神仍然没有超过40分的：

边权\*2因为要逃跑；

时限-1因为要逃跑；

玄妙的数组大小；

Return见祖宗 ；

#include<cstdio> #include<iostream> using namespace std; typedef long long ll; int tl; int f[1010][1010]; struct item { int dis; int bny; int lc,rc; int vl[45],fee[45]; }e[610]; void build(int r) { scanf("%d%d",&e[r].dis,&e[r].bny); e[r].dis*=2; if(!e[r].bny) { e[r].lc=r*2;build(r*2); e[r].rc=r*2+1;build(r*2+1); for(int i=e[r].dis;i<=tl;i++) for(int j=0;j<=i-e[r].dis;j++)f[r][i]=max(f[r][i],f[e[r].lc][j]+f[e[r].rc][i-j-e[r].dis]); } else { for(int i=1;i<=e[r].bny;i++) scanf("%d%d",&e[r].vl[i],&e[r].fee[i]); for(int i=1;i<=e[r].bny;i++) for(int j=tl;j>=e[r].fee[i];j--) if(j-e[r].fee[i]>=e[r].dis) f[r][j]=max(f[r][j],f[r][j-e[r].fee[i]]+e[r].vl[i]); return ; } } int main() { scanf("%d",&tl); tl--; build(1); cout<<f[1][tl]<<endl; return 0; }

转载于:https://www.cnblogs.com/Rorschach-XR/p/10969104.html

发表评论取消回复

表情：

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

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

相关阅读

相关算法：工作窃取算法（work-stealing）。

工作窃取算法是指某个线程从其他队列里窃取任务来执行。那么，为什么需要使用工作窃取算法呢？假如我们需要做一个比较大的任务，可以把这个任务分割为若干互不依赖的子任务，为了减少线程间

快来打我*/ 2024年02月19日 14:32/ 0 赞/ 37 阅读

相关不重启JVM，替换掉已经加载的类，偷天换日？

来源 | 美团技术博客在遥远的希艾斯星球爪哇国塞沃城中，两名年轻的程序员正在为一件事情苦恼，程序出问题了，一时看不出问题出在哪里，于是有了以下对话： “Debug一

蔚落/ 2023年10月04日 15:25/ 0 赞/ 5 阅读

相关不重启JVM，替换掉已经加载的类，偷天换日？

![0D5F937FE12312312D81F17F.jpg][] 程序员的成长之路互联网/程序员/技术/资料共享 [关注][Link 1] 阅读本文大概需要 10

古城微笑少年丶/ 2023年01月21日 02:17/ 0 赞/ 109 阅读

相关偷天换日，逼真的天空置换算法

![偷天换日，逼真的天空置换算法][eb9d2fd9e39f90df650c56883a4020c7.png] > 点赞再看，养成习惯，微信公众号搜索【JackCui-AI】

柔情只为你懂/ 2022年11月20日 09:38/ 0 赞/ 99 阅读

相关 How to be successful: steal ideas and copy people

I landed in Lagos at midday, and stepped out of the plane into the african sunlight. Pol

痛定思痛。/ 2022年07月16日 14:09/ 0 赞/ 121 阅读

相关 SqlServer支持 select * from (select *from tablename)

对于这个问题，网上有的人说是不支持的。实际上给内部的表起个别名就可以了。 select \ from ( select \ from products ) a --这里a

清疚/ 2022年07月14日 15:26/ 0 赞/ 472 阅读

相关工作窃取算法 work-stealing

工作窃取(work-stealing)算法是指某个线程从其他队列里窃取任务来执行。一个大任务分割为若干个互不依赖的子任务，为了减少线程间的竞争，把这些子任务分别放到不同的

叁歲伎倆/ 2022年05月21日 11:56/ 0 赞/ 151 阅读

相关理解CPU steal time

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] Netflix 很关注CPU的Steal Time。他

迈不过友情╰/ 2022年01月13日 12:19/ 0 赞/ 114 阅读

相关偷天换日（树形DP）

[洛谷][Link 1] 比较喜欢(≧∇≦)ﾉ这个建图对于叶子节点，直接处理出f\[i\]\[j\]当前i号节点分j个时间 include<bits/stdc

Dear 丶/ 2021年11月09日 08:04/ 0 赞/ 326 阅读

相关 Steal 偷天换日题解(From luoguBlog)

树形+背包奇奇怪怪的dp。考试的时候费了半天劲把题读完后思路基本正解，然而也不知道为什么脑子鬼畜了一下打了个非递归建树？而且链式前向星建边？岔路口和藏品都搞成

我就是我/ 2021年10月29日 08:50/ 0 赞/ 153 阅读