Steal 偷天换日 题解(From luoguBlog)
2024-08-31 02:08:55
树形+背包 奇奇怪怪的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;
}
最新文章
- ASP.NET MVC5+EF6+EasyUI 后台管理系统(53)-工作流设计-我的批阅
- (转载)AppScan使用分享
- App_Offline.htm 功能
- 对Jena的简单理解和一个例子
- ☀【插件】iScroll
- UVA11387 - The 3-Regular Graph(推理)
- 点击页面其它地方隐藏该div的方法
- Entity Framework : The model backing the &#39;&#39; context has changed since the database was created
- Netty的常用概念
- cesium 之地图显示坐标、比例尺、海拔高度效果篇(附源码下载)
- Hdoj 2188.悼念512汶川大地震遇难同胞——选拔志愿者 题解
- hdu 4122 Alice&;#39;s mooncake shop (线段树)
- Beans
- C简介与环境配置
- Linux shell(4)
- Mybatis头文件
- 02--CSS的继承性和层叠性
- Fn+F1-F12,避免使用FN+
- python 自定义函数表达式 拟合求系数
- beego——高级查询
热门文章
- hdu 2527哈夫曼树(二叉树的运用)
- nyoj_102_次方求模_201308221547
- [bzoj1103][POI2007]大都市meg_dfs序_树状数组
- Spring MVC-处理程序映射(Handler Mapping)-控制器类名称处理程序映射(Controller Class Name Handler Mapping)示例(转载实践)
- ZooKeeper动态增加Server(动态增加节点)的研究(待实践)
- iOS:解决pod的Insecure world writable dir问题
- Xposed获取微信usernamepassword
- jenkins任务失败重新构建插件Naginator Plugin
- Android实战简易教程-第二十四枪(基于Baas的用户表查询功能实现!)
- POJ 2421--Constructing Roads【水题 &;amp;&;amp; 最小生成树 &;amp;&;amp; kruskal】