组队赛的时候的一道题，那个时候想了一下感觉dp不怎么好写呀，现在写了出来，交上去过了，但是我觉得我还是应该WA的呀，因为总感觉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 |
#pragma warning(disable:4996)#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<string>#include<vector>#define maxn 150using
namespace std;struct
Edge{ int
v, w; Edge(int
vi, int
wi) :v(vi), w(wi){} Edge(){}};vector<Edge> G[maxn];int
n, q;int
dp[maxn][maxn];int
tmp[maxn];void
dfs(int
u, int
fa){ for
(int i = 0; i < G[u].size(); i++){ int
v = G[u][i].v, w = G[u][i].w; if
(v == fa) continue; dfs(v, u); memcpy(tmp, dp[u], sizeof(dp[u])); for
(int k = q; k >= 0; k--){ for
(int j = k - 1; j >= 0; j--){ dp[u][k] = max(dp[u][k], dp[v][j] + tmp[k-1- j] + w); } } }}int
main(){ while
(cin >> n >> q) { for
(int i = 0; i <= n; i++) G[i].clear(); int
ui, vi, wi; for
(int i = 0; i < n - 1; i++){ scanf("%d%d%d", &ui, &vi, &wi); G[ui].push_back(Edge(vi, wi)); G[vi].push_back(Edge(ui, wi)); } memset(dp, 0, sizeof(dp)); dfs(1, -1); cout << dp[1][q] << endl; } return
0;} |
URAL1018 Binary Apple Tree(树dp),布布扣,bubuko.com
URAL1018 Binary Apple Tree(树dp)
原文：http://www.cnblogs.com/chanme/p/3631969.html