題目鏈接：點擊查看

題目大意：每個人都有一個快樂值，給定一個樹狀的從屬關系，僅當上司和下屬都不在的時候這個個人的快樂值才能表現出來，問怎么樣才能讓整體的快樂值達到最大

題目分析：做線段樹做吐了，來換換思維，入門的樹形dp題一道，樹形dp，簡明扼要的說就是在樹上做的動態規劃，那么就離不開轉移方程了，這個題的狀態有兩個，來或者不來，有點像背包問題的選與不選，那么我們就假設dp[i][j]代表第i個人的狀態為j時的最大快樂值，j分為0或1，0代表不來，1代表來，那么可以將第i個人視為根節點，然后遞歸到葉節點再往上逐層更新即可，這個題的轉移方程還算簡單的：

dp[i][0]+=max(dp[j][0],dp[j][1])，j為i的兒子，因為i不去，所以j去不去無所謂

dp[i][1]+=dp[j][0]，j為i的兒子，因為i要去，所以j不能去

這個題還有個關鍵點是找到根節點然后dfs，我是用的入度的關系，根節點的入度一定為0，所以加一個輔助數組來記錄一下每條邊的入度就好了

直接上代碼了：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=6e3+100;int dp[N][2];//dp[i][0]表示當i為根節點時i位置不放的最大值，dp[i][1]表示當i為根節點時i位置放的最大值 //所以dp[i][0]+=max(dp[j][0],dp[j][1])j為i的兒子，因為i不去，所以j去不去無所謂 //dp[i][1]+=dp[j][0]j為i的兒子，因為i要去，所以j不能去vector<int>node[N];int num[N];//用來存儲每個點的入度，若入度為0，則為根節點void dfs(int u) {for(int i=0;i<node[u].size();i++){int v=node[u][i];dfs(v);dp[u][0]+=max(dp[v][0],dp[v][1]);dp[u][1]+=dp[v][0];} }int main() { // freopen("input.txt","r",stdin);int n;while(scanf("%d",&n)!=EOF){for(int i=1;i<=n;i++){scanf("%d",&dp[i][1]);node[i].clear();}memset(num,0,sizeof(num));int u,v;while(scanf("%d%d",&v,&u)!=EOF&&v+u){node[u].push_back(v);num[v]++;}int root;for(int i=1;i<=n;i++)if(!num[i]){root=i;break;}dfs(root);cout<<max(dp[root][0],dp[root][1])<<endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ - 2342 Anniversary party(树形dp入门)的全部內容，希望文章能夠幫你解決所遇到的問題。

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