HDU - 6201 transaction transaction transaction(树形dp)
transaction transaction transactionTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 132768/132768 K (Java/Others)Total Submission(s): 2964 Accepted Submission(s): 1328 Problem Description 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.
Input The first line contains an integer T (1≤T≤10 ) , the number of test cases.
Output For each test case, output a single number in a line: the maximum money he can get.
Sample Input 1 4 10 40 15 30 1 2 30 1 3 2 3 4 10
Sample Output 8
Source 2017 ACM/ICPC Asia Regional Shenyang Online
Recommend liuyiding |
每个城市都有种个价格，走每条路都要花费一种价格，问在哪里买一本书再卖到那里去能使得利益最大化。
我用dp[u][0]来表示从已遍历的某个点买书再走到到这里的最小的花费是多少（负数），用dp[u][1]来表示从已遍历的某个点卖书前走到到这里得到的最大利益是多少。然后每个点进行一次比较并更新ans值就好了。不过这样做需要注意的一个地方就是在便利到最后一个点的时候。。我们需要额外进行一次更新，就是对dp[u][0]+dp[u][1]与ans的更新就好了。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int dp[maxn][3], val[maxn], head[maxn];//dp[][0]是买,dp[][1]是卖
int ans = 0;
struct *** {
int v, w, ne;
}ed[maxn << 1];
int n, m, cnt;
void add(int u,int v,int w) {
ed[cnt].v = v; ed[cnt].w = w;
ed[cnt].ne = head[u]; head[u] = cnt++;
}
void init() {
memset(head, -1, sizeof head);
cnt = ans = 0;
memset(dp, 0, sizeof dp);
}
void dfs(int u,int fa) {//dp[][0]是买后走到,dp[][1]是卖前走到
int cost = -val[u], get = val[u];
for (int i = head[u]; ~i; i = ed[i].ne) {
int v = ed[i].v;
if (v == fa)continue;
dfs(v, u);
cost = max(dp[v][0] - ed[i].w, cost);
get = max(dp[v][1] - ed[i].w, get);
}
ans = max(cost + val[u], ans);
ans = max(get - val[u], ans);
dp[u][0] = cost;
dp[u][1] = get;
// cout << u << " : " << cost << " " << get << endl;
}
int main() {
int te;
scanf("%d", &te);
while (te--) {
init();
scanf("%d", &n);
for (int s = 1; s <= n; s++) scanf("%d", &val[s]);
for (int i = 1; i < n; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c); add(b, a, c);
}
dfs(1,0);
ans = max(ans, dp[1][0] + dp[1][1]);;
printf("%d\n", ans);
}
}
