生活随笔
收集整理的這篇文章主要介紹了
洛谷 [P1352] 没有上司的舞会
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
樹型DP
一個人不能和他的直接上司一起去,那么就分別保存這個人去和不去的最大值
注意轉移方程
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 7005;
int n, num[MAXN], dp[MAXN][2], fa[MAXN], head[MAXN], nume, rot;
struct edge{int to, nxt;
}e[MAXN<<1];
void adde(int from, int to) {e[++nume].to = to;e[nume].nxt = head[from];head[from] = nume;
}
void dfs(int rt) {dp[rt][1] = num[rt];for(int i = head[rt]; i; i = e[i].nxt) {int v = e[i].to;if(v == fa[rt]) continue;dfs(v);if(dp[v][1] > dp[v][0]) dp[rt][0] = max(dp[rt][0], dp[rt][0] + dp[v][1]);else dp[rt][0] = max(dp[rt][0], dp[rt][0] + dp[v][0]);dp[rt][1] = max(dp[rt][1], dp[rt][1] + dp[v][0]);}
}
int main() {cin >> n;for(int i = 1; i <= n; i++) cin >> num[i];for(int i = 1; i< n; i++) {int u, v;cin >> u >> v;fa[u] = v;adde(u, v); adde(v, u);}for(int i = 1; i <= n; i++) if(!fa[i]) rot = i;dfs(rot);cout << max(dp[rot][0], dp[rot][1]) << endl;return 0;
}
轉載于:https://www.cnblogs.com/Mr-WolframsMgcBox/p/8607449.html
總結
以上是生活随笔為你收集整理的洛谷 [P1352] 没有上司的舞会的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
