hdu 1520 Anniversary party
題意：
某人要開一個聚會，每個人都有一個自己的交際評分，但是他們都不想和自己的直接上司在一起，那樣會不開心，所以只讓一部分人來，希望你能找出評分最大的方案。
解析：
關于上司下級的事情，就會涉及一點并查集，不過這題和并查集沒有太大關系，需要建樹來維系他們之間的關系，然后用樹狀dp來寫，狀態轉移方程式為dp[i][0]+=max(dp[j][1],dp[i][0]),dp[i][1]+=dp[j][0];i表示父節點，j為子節點,0的意思是i或j沒有出席m，1表示i或j出席了，也就是如果父節點沒有出席，子節點可以出席也可以不出席，如果父節點出席了，子節點一定不能出席。
代碼:
#include <iostream> #include <stdio.h> #include <string.h> #include <math.h> #include <algorithm> #include <queue> #include <vector> using namespace std; #define N 6005 #define oo 0x3f3f3f3f vector<int>G[N]; int n,dp[N][2],father[N]; void dfs(int root) { for(int i=0;i<G[root].size();i++) { dfs(G[root][i]); } for(int i=0;i<G[root].size();i++) { dp[root][0]+=max(dp[G[root][i]][0],dp[G[root][i]][1]); dp[root][1]+=dp[G[root][i]][0]; } } int main() { int u,v; while(~scanf("%d",&n)) { memset(father,-1,sizeof(father)); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { scanf("%d",&dp[i][1]); G[i].clear(); } while(scanf("%d%d",&u,&v)&&(u+v)) { father[u]=v; G[v].push_back(u); } int root=1; while(father[root]!=-1) root=father[root]; dfs(root); printf("%d\n",max(dp[root][1],dp[root][0])); } }
浙公網安備 33010602011771號