HDU 4276 The Ghost Blows Light(树型DP)

题目大意

给定一棵 $N$ 个节点的树,点上有价值为 $A_i$,边上有时间花费 $t_j$。要求从编号 $1$ 的节点出发,到达编号为 $N$ 的节点,问是否能在给定的 $T$ 时间里到达,若能,输出可以获得的最大价值。每个节点的价值只能算一次,但边每走一次都得消耗时间。
$(1 \le n \le 100, 0 \le T \le 500, 0 \le A_i \le 100, 0 \le t_j \le 100)$

解题思路

树型DP

先 DFS 算出从 $1$ 号点到 $N$ 号点的最小花费,若大于时间 $T$ 直接输出。否则将之前 DFS 到的路径上的花费赋为 $0$,然后直接 树型DP 就可以了。

$dp[i][j]$ 表示在 $i$ 点花费时间 $j$ 所能获得的最大价值。由于必走路径上的花费已赋为 $0$,那么 $dp$ 时必会取到路径上节点的价值。然后状态方程转移的原理类似于01背包,只不过多了一层枚举子节点花费多少时间,这是跟普通01背包不同的地方,普通01背包是固定花费多少价值多少,而这里是枚举花费多少价值多少。

详细请看代码。

Ps: DP还是太弱啦QAQ,以后DP还是得多做点题目。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e2 + 10;

struct Edge {
int to, cost, next;
Edge( int to = 0, int cost = 0, int next = 0 ) : to(to), cost(cost), next(next) {}
} G[MAXN << 1];
int n, T;
int a[MAXN];
int tot, head[MAXN];
int dp[MAXN][MAXN << 3];

void init()
{

tot = 0;
memset(head, -1, sizeof(head));
}
void addEdge(int u, int v, int cost)
{

G[tot] = Edge(v, cost, head[u]);
head[u] = tot++;
G[tot] = Edge(u, cost, head[v]);
head[v] = tot++;
}
int findPath(int u, int pre, int cost)
{

if( u == n ) return cost;
for( int i = head[u]; ~i; i = G[i].next ) {
Edge &e = G[i];
if( e.to == pre ) continue;
int d = findPath(e.to, u, cost + e.cost);
if( d ) {
e.cost = 0;
G[i ^ 1].cost = 0;
return d;
}
}
return 0;
}
void dfs(int u, int pre)
{

fill(dp[u], dp[u] + T + 1, a[u]);
for( int i = head[u]; ~i; i = G[i].next ) {
Edge &e = G[i];
if( e.to == pre ) continue;
int temp = e.cost << 1;
dfs(e.to, u);
for( int j = T; j >= temp; -- j ) { // 倒序枚举,原理同一维01背包
for( int k = temp; k <= j; ++ k ) {
dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[e.to][k - temp]);
}
}
}
}
int main()
{

while( ~scanf("%d %d", &n, &T) ) {
init();
int x, y, t;
for( int i = 0; i < n - 1; ++ i ) {
scanf("%d %d %d", &x, &y, &t);
addEdge(x, y, t);
}
for( int i = 1; i <= n; ++ i ) {
scanf("%d", a + i);
}
int cost = findPath(1, -1, 0);
if( cost > T ) {
puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!");
continue;
}
T -= cost;
dfs(1, -1);
printf("%d\n", dp[1][T]);
}
return 0;
}

知识扩展

  • 01背包:先枚举物品,再逆序枚举容量
  • 完全背包:先枚举物品,再正序枚举容量
  • 分组背包:先逆序枚举容量,再枚举物品(最外层枚举每一组)
如果您觉得这篇博文对您有所帮助,可以考虑请我吃颗糖哦!