还是 树形dp QAQ……

　　很开心是第305个通过的（嘿嘿嘿）~

　　是上一道题的升级版，但是其实只要把到展厅后简单的除法改成01背包就可以了。

　　有一点忘记强调了（莫怪）：

　　为了保证我们的主人公活着逃出去，所以他至少要在警察来的前一秒钟逃走，所以给他的最长时间是 n - - 。

　　代码：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define maxn 1005#define int long long int f[maxn][maxn],v[maxn],c[maxn],n,num=1;void dfs(int u){    int t,x;    scanf("%lld%lld",&t,&x);    t*=2;    if(x)    {        for(int i=1; i<=x; i++)            scanf("%lld%lld",&c[i],&v[i]);        for(int i=1; i<=x; i++)            for(int j=n; j>=0; j--)                if(j-v[i]>=t)                    f[u][j]=max(f[u][j],f[u][j-v[i]]+c[i]);        return ;    }    int l=++num;    dfs(l);    int r=++num;    dfs(r);    for(int i=t; i<=n; i++)        for(int j=0; j<=i-t; j++)            f[u][i]=max(f[u][i],f[l][j]+f[r][i-j-t]);}main(){    scanf("%lld",&n);    n--;    dfs(1);    printf("%lld",f[1][n]);    return 0;}