题目描述
经过数月的精心准备，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 ;
}