HDU 1520 Anniversary party（樹形dp）

樹形dp第一題！！！

題意很清晰，思路也很明確。很容易找到根節點，即最大的boss，通過根節點向下dp。

狀態轉移方程：

?

• int to = vec[x][i];
• dfs(to);
• dp[x][1] += dp[to][0];
• dp[x][0] += max(dp[to][1], dp[to][0]);

即對于一個節點。如果它有根節點：

• 選區本節點；
• 或者選取根節點的最大權值.

?

#include <iostream> #include <cstring> #include <vector>using namespace std;const int N = 6010;int n; int value[N]; vector< vector<int > > vec(N); int boss, emp; int root; int non[N];int dp[N][2];void init() {memset(value, 0,sizeof(value));memset(non, false,sizeof(non));memset(dp, 0,sizeof(dp)); }void find_root() {for(int i = 1 ; i <= n ;i++){if(non[i] == false){root = i;return;}} }void dfs(int x) {for(int i = 0; i < (int)vec[x].size(); i++){int to = vec[x][i];dfs(to);dp[x][1] += dp[to][0];dp[x][0] += max(dp[to][1], dp[to][0]);} }int main() {init();cin >> n;for(int i = 1 ; i <= n ; i++) {cin >> value[i];dp[i][1] = value[i];}for(int i = 1 ; i < n ; i++){cin >> boss >> emp;vec[emp].push_back(boss);non[boss] = true;}cin >> boss >> emp;find_root();dfs(root);cout << max( dp[root][0] , dp[root][1] );return 0; }

?

轉載于:https://www.cnblogs.com/ronnielee/p/9495148.html

總結

以上是生活随笔為你收集整理的HDU 1520 Anniversary party（树形dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。