ICPC2017网络赛（沈阳）1008 transaction transaction transaction——树形DP

HDU 6201

Kelukin is a businessman. Every day, he travels around cities to do some business. On August 17th, in memory of a great man, citizens will read a book named "the Man Who Changed China". Of course, Kelukin wouldn't miss this chance to make money, but he doesn't have this book. So he has to choose two city to buy and sell. As we know, the price of this book was different in each city. It is ai yuan in it city. Kelukin will take taxi, whose price is 1yuan per km and this fare cannot be ignored.There are n−1 roads connecting n cities. Kelukin can choose any city to start his travel. He want to know the maximum money he can get.

定义dp[i][j]为第i个城市【从它的子树中】买(0)或者卖(1)书所得的最大利润

状态转移方程为：dp[u][0] = max(dp[u][0], dp[v][0] - cost);

dp[u][1] = max(dp[u][1], dp[v][1] - cost);

求解ans只要：

ans = max(ans, dp[u][0] + dp[u][1]);

#include #include #include #include #include #include using namespace std;typedef pair P;using namespace std;const int maxn = 1e5 + 10;int T, n, ans, a[maxn], dp[maxn][2];vector

G[maxn];void dfs(int u, int par) { dp[u][0] = -a[u], dp[u][1] = a[u]; for (int i = 0; i < G[u].size(); i++) { int v = G[u][i].first, cost = G[u][i].second; if (v == par) continue; dfs(v, u); dp[u][0] = max(dp[u][0], dp[v][0] - cost); dp[u][1] = max(dp[u][1], dp[v][1] - cost); } ans = max(ans, dp[u][0] + dp[u][1]);}int main() { scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); G[i].clear(); } for (int i = 1; i <= n - 1; i++) { int u, v, cost; scanf("%d %d %d", &u, &v, &cost); G[u].push_back(make_pair(v, cost)), G[v].push_back(make_pair(u, cost)); } ans = 0; dfs(1, -1); printf("%d\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。