提交地址：http://www.cqoi.net:2012/JudgeOnline/problem.php?id=1286

这题是OI的经典题，不难，注意一点，原题是用文件输入输出的，但是这里的提交直接标准输入输出即可

这题的题意很清晰，明说了是二叉树（而且只能在两个孩子的节点和叶子节点）。

注意输入给出的信息，对于一对数据，a，b，a指通过走廊的时间，那是不是树中边的信息呢？不是的，应该是点的信息。树中每一个点都应该包含两个信息，就是时间花费和它有多少张画，对于非叶子节点而言，它的画数都是0，而时间是有的，对于叶子节点，除了有画数外，它也是有时间花费的

另外，本题读题要仔细，它是说在警察来之前就要离开，而不能在他来的时候离开，所以读入警察的到达时间后减1再开始计算

另外偷东西是要进去和出来的，所以如果经过了某个点往下走，就必定会经该店返回（树的性质可知），所以花费其实是两倍，所以我们在一开始保存点的花费的时候，就直接将时间花费保存为两倍，这样就相当于做到了返回

 

最后说一次DP思想

dp[rt][time]表示在rt这个点，剩下time时间能偷到最多的画

1.虽然时间有time，但要先花费掉通过该点的时间，tt=time-t[rt].cost

2.然后在tt时间内dp，dp[rt][time]= max{ dp[lch][i] + dp[rch][tt-i] }

这个方程很容易理解，一半时间去左边偷一半时间去右边偷，两者相加，再取最大值

3.而对于叶子节点，同样有时间花费的，所以同样先计算出tt，但是计算出tt后不用再递归了，而是计算在tt时间内最多可以拿多少画，并且这里肯定是尽量拿，只要时间还够的

但是注意一点，不能tt/5,因为时间够，但是可能画不够。。。我就是这样纠结了一下，才想起这个问题

至于怎么建树，输入已经是按照前序遍历序列给出的，那么就顺着输入，来个递归建树即可

 

#include 
     
      #include 
      
       #include 
       
        using namespace std;#define N 550#define T 650#define max(a,b) ((a)>(b)?(a):(b))int n;struct node{    int lch,rch,cost,val;}t[N];pair
        
         a[N];int dp[N][T];void build(int &m){    int rt=m;    t[rt].cost=2*a[rt].first; t[rt].val=a[rt].second;    if(a[m].second)    {        t[rt].lch=t[rt].rch=-1;        return ;    }    t[rt].lch=m+1;    build(++m);    t[rt].rch=m+1;    build(++m);}int dfs(int rt ,int time){    if(dp[rt][time]!=-1) return dp[rt][time];    if(time==0) return dp[rt][time]=0;        if(t[rt].lch==-1) //叶子    {        int c;        if(t[rt].val*5 <= time-t[rt].cost) c=t[rt].val;        else   c=(time-t[rt].cost)/5;        return dp[rt][time]=c;    }    dp[rt][time]=0;    int tt=time-t[rt].cost;    for(int i=0; i<=tt; i++) //枚举左孩子可以使用的时间    {        int s1=dfs(t[rt].lch , i);        int s2=dfs(t[rt].rch , tt-i);        dp[rt][time]=max(dp[rt][time] , s1+s2);    }    return dp[rt][time];}int main(){    int time;    scanf("%d",&time); time--;    n=0;    while(scanf("%d%d",&a[n].first,&a[n].second)!=EOF) n++;    int m=0;    build(m);    memset(dp,-1,sizeof(dp));    dfs(0,time);    printf("%d\n",dp[0][time]);    return 0;}