总结
1. dp[u][k] 是恰好用完 k 时间的最大价值
2. dfs(u, pre, vmax) 是计算 dp[u][1...vmax] 的值
3. dfs 内部遍历, j 从大到小, 防止重复计算 f(j) = g(j-k)
而 k 是从小到大, 想不通为什么
代码
|
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145 |
/* * source.cpp * * Created on: Apr 6, 2014 * Author: sangs */#include <stdio.h>#include <iostream>#include <string>#include <vector>#include <memory.h>#include <queue>#include <set>#include <algorithm>#include <math.h>using
namespace std;class
Road {public: int
to, cost; Road(int
_to, int
_cost):to(_to), cost(_cost) {} Road() { to = cost = 0; } bool
operator <(const
Road &rhs) const
{ return
this->cost < rhs.cost; }};vector<Road> graph[1000];int
val[1000];int
dp[1000][1000];const
int INF = 0X3F3F3F3F;int
dist[1000];int
father[1000];bool
mark[1000]; // mark those nodes must passbool
visited[1000];/* * calculate the shortest path from 1 to n * as well as those nodes in shortest path * SPFA algorithm */int
bfs(int
n) { queue<int> record; memset(visited, 0, sizeof(visited)); memset(mark, 0, sizeof(mark)); memset(dist, 0x3f, sizeof(dist)); record.push(1); dist[1] = 0; father[1] = -1; while(!record.empty()) { int
thisNode = record.front(); record.pop(); for(size_t
i = 0; i < graph[thisNode].size(); i ++) { int
j = graph[thisNode][i].to; //cout << j << " " << dist[i] << " " << graph[thisNode][i].cost << endl; if(dist[thisNode] + graph[thisNode][i].cost < dist[j]) { dist[j] = dist[thisNode] + graph[thisNode][i].cost; father[j] = thisNode; record.push(j); } } } for(int
i = n; i != -1; i = father[i]) { mark[i] = 1; } return
dist[n];}/* * tree_dp to calculate dp[u][1...vmax] * dp[u][k] is the maximum income when assigned k time to node u and get back to u * pre is u‘s father */void
tree_dp(int
u, int
pre, int
vmax) { dp[u][0] = val[u]; for(size_t
i = 0; i < graph[u].size(); i ++) { // enum v‘s child int
index = graph[u][i].to; if(index == pre) continue; if(mark[index]) continue; tree_dp(index, u, vmax); int
cost = graph[u][i].cost; for(int
j = vmax; j >= 0; j --) { for(int
k = 0; k <= j-2*cost; k ++) { dp[u][j] = max(dp[u][j], dp[u][j-k-2*cost]+dp[index][k]); } } }}int
main() { freopen("input.txt", "r", stdin); int
n, T; while(scanf("%d%d", &n, &T) != EOF) { for(int
i = 0; i <= n+10; i ++) graph[i].clear(); for(int
i = 0; i < n-1; i ++) { int
from, to, cost; scanf("%d%d%d", &from, &to, &cost); graph[from].push_back(Road(to, cost)); graph[to].push_back(Road(from, cost)); } for(int
i = 1; i <= n; i ++) scanf("%d", val+i); int
cutTime = bfs(n); T -= cutTime; memset(dp, 0, sizeof(dp)); dp[n+1][0] = 0; for(int
i = 1; i <= n; i ++) { if(mark[i] == 0) continue; tree_dp(i, n+1, T); for(int
j = T; j >= 0; j --) { for(int
k = 0; k <= j; k ++) { //for(int k = j; k >= 0; k --) { dp[n+1][j] = max(dp[n+1][j], dp[n+1][j-k] + dp[i][k]); } } } int
res = 0; for(int
i = 0; i <= T; i ++) res = max(res, dp[n+1][i]); printf("%d\n", res); } return
0;} |
HDOJ 4276 鬼吹灯 (树形DP),布布扣,bubuko.com
原文：http://www.cnblogs.com/zhouzhuo/p/3651652.html