洛谷P3360偷天换日（树形DP）

题目描述

艺术馆由若干个展览厅和若干条走廊组成。每一条走廊的尽头不是通向一个展览厅，就

是分为两个走廊。每个展览厅内都有若干幅画，每副画都有一个价值。经过走廊和偷画都是

要耗费时间的。

警察会在n 秒后到达进口，在不被逮捕的情况下你最多能得到的价值。

输入

第一行一个整数 n(n≤600)。

第二行若干组整数，对于每组整数（t,x），t 表示进入这个展览厅或经过走廊要耗费 t

秒的时间，若x>0 表示走廊通向的展览厅内有x 幅画,接下来

x对整数(w,c)表示偷一幅价值为 w 的画需要 c秒的时间。若

x=0 表示走廊一分为二。(t，c≤5; x≤30)

输入是按深度优先给出的。房间和走廊数不超过 300 个。

输出

仅一个整数，表示能获得的最大价值。

Sample

50 
5 0 10 1 10 1 5 0 10 2 500 1 1000 2 18 1 1000000 4 

1500

分析

这道题和选课类似。

题目看着很复杂，但其实很简单。

给出一个代价，求出能获得的最大价值。

注意这里的最大代价是n-1，因为在第n秒，警察已经到了。（坑死我了 ?? ）

注意输入是按dfs序给出的，我们可以边dfs边读入。

一条路的末端要么有画，要么分成两条路。

有画时，我们做01背包就可以。

分成两条路时，对两个儿子分别dp。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int maxn = 10001;
int n, m, dp[maxn][maxn], w[maxn], c[maxn];//dp[i][j]以i为根，花费j的代价获得的最大价值
void dfs(int u){
    int x, y; scanf("%lld%lld", &x, &y);
    x <<= 1;//往返
    if(y){//有奶酪
        for(int i=1; i<=y; i++) scanf("%lld%lld", &w[i], &c[i]);
        for(int i=1; i<=y; i++)//枚举奶酪数
            for(int j=n; j>=c[i]+x; j--)//枚举花费的代价
                dp[u][j] = max(dp[u][j], dp[u][j-c[i]]+w[i]);
    }
    else{//无
        dfs(u<<1); dfs(u<<1|1);//两个儿子
        for(int j=x; j<=n; j++)//在以u为根的树上花的时间
            for(int k=0; k<=j-x; k++)//走左儿子花的时间
                dp[u][j]=max(dp[u][j],dp[u<<1][j-k-x]+dp[u<<1|1][k]);
    }
}
signed main(){
    scanf("%lld", &n);
    n--;//大坑！
    dfs(1);
    printf("%lld\n", dp[1][n]);
    return 0;
}

洛谷P3360偷天换日（树形DP）

原文：https://www.cnblogs.com/hzoi-poozhai/p/12758480.html