P1270 “访问”美术馆
题目描述
经过数月的精心准备,Peer Brelstet,一个出了名的盗画者,准备开始他的下一个行动。艺术馆的结构,每条走廊要么分叉为两条走廊,要么通向一个展览室。Peer知道每个展室里藏画的数量,并且他精确测量了通过每条走廊的时间。由于经验老到,他拿下一幅画需要5秒的时间。你的任务是编一个程序,计算在警察赶来之前,他最多能偷到多少幅画。
输入输出格式
输入格式:
第1行是警察赶到的时间,以s为单位。第2行描述了艺术馆的结构,是一串非负整数,成对地出现:每一对的第一个数是走过一条走廊的时间,第2个数是它末端的藏画数量;如果第2个数是0,那么说明这条走廊分叉为两条另外的走廊。数据按照深度优先的次序给出,请看样例。
一个展室最多有20幅画。通过每个走廊的时间不超过20s。艺术馆最多有100个展室。警察赶到的时间在10min以内。
输出格式:
输出偷到的画的数量
输入输出样例
60
7 0 8 0 3 1 14 2 10 0 12 4 6 2
2
Solution:
本题是很有技巧性的树形$dp$。。。
首先我们一定要读题仔细(我开始就没细看搞了半天~),注意几个关键信息:
1、给定的一定是一棵完满二叉树(所有非叶子结点的度都是2)。
2、时间不会超过$600s$ 。
3、警察来之前取完,意味着求的是$s-1$的时间范围内取的最大价值。
4、不要忘了取一件耗费$5s$时间,且一段路要走两次,时间翻倍。
然后由上面第一条可以得出一个很简单的读入方法:每次读入时,若价值为$0$,则一定有两个子节点,于是递归读入(类似线段树建树)。
那么我们定义状态$f[i][j]$表示在$i$节点耗费$j$时间能取得的最多件数,不难得到状态转移方程:$f[i][j]=max(f[i][j],f[i<<1][k]+f[i<<1|1][j-k-t[v]])$(在左右子树中取),注意一下搜索时的边界问题就好了。
代码:
#include<bits/stdc++.h>
#define il inline
#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)>(b)?(b):(a))
using namespace std;
const int N=;
int n,s,w[N],v[N],cnt,f[N][N<<]; il void init(int u){
cin>>v[u]>>w[u];
v[u]<<=;
if(!w[u]) init(u<<),init(u<<|);
} il int dfs(int u,int t){
if(f[u][t]||!t) return f[u][t];
if(w[u])return f[u][t]=Min(w[u],(t-v[u])/);
For(k,,t-v[u]) f[u][t]=Max(f[u][t],dfs(u<<,k)+dfs(u<<|,t-v[u]-k));
return f[u][t];
} int main(){
ios::sync_with_stdio();
cin>>s;
init();
cout<<dfs(,s-);
return ;
}
最新文章
- CentOS6.5安装Eclipse
- jsonp接口的xss防范
- js做计算器
- AngularJs angular.bind、angular.bootstrap、angular.copy
- VISIBLE、INVISIBLE、GONE的区别
- NPOI.dll学习
- 不一样的风格,C#的lambda表达式
- Android Camera 使用一例,视频聊天app
- Solr 按照得分score跟指定字段相乘排序
- Spring框架入门之基于xml文件配置bean详解
- java如何获得数据库表中各字段的字段名
- 检查Json格式工具
- 经度和纬度在SQL中的数据类型
- maven wrapper使用本地maven
- Pyhon 逻辑运算符
- 回调函数: 一定要在函数名前加上 CALLBACK,否则有可能引起内存崩溃!
- Executors与ThreadPoolExecutor
- ubuntu下nodejs源码安装
- Visual studio 2010出现“error LNK1123: 转换到 COFF 期间失败: 文件无效或损坏”解决方式
- 常用模块:re ,shelve与xml模块