| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 5767 | Accepted: 3335 |
Description
Input
Output
Sample Input
7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0
Sample Output
5
题意：
某公司要举办一次晚会，但是为了使得晚会的气氛更加活跃，每个参加晚会的人都不希望在晚会中见到他的直接上司，现在已知每个人的活跃指数和上司关系（当然不可能存在环），求邀请哪些人（多少人）来能使得晚会的总活跃指数最大。
思路：
任何一个点的取舍可以看作一种决策，那么状态就是在某个点取的时候或者不取的时候，以他为根的子树能有的最大活跃总值。分别可以用f[i,1]和f[i,0]表示第i个人来和不来。
当i来的时候，dp[i][1] += dp[j][0];//j为i的下属
当i不来的时候，dp[i][0] +=max(dp[j][1],dp[j][0]);//j为i的下属
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 using namespace std; 6 #define Max 6005 7 bool vis[Max]; 8 int dp[Max][2],fa[Max],num[Max]; 9 int n; 10 void tree_dp(int node) 11 { 12 int i,j; 13 vis[node]=1; 14 for(i=1;i<=n;i++) 15 { 16 if(vis[i]==0&&fa[i]==node) 17 { 18 tree_dp(i); 19 dp[node][1]+=dp[i][0]; 20 dp[node][0]+=max(dp[i][0],dp[i][1]); 21 } 22 } 23 } 24 int main() 25 { 26 int i,j; 27 int a,b; 28 int root; 29 freopen("in.txt","r",stdin); 30 while(scanf("%d",&n)!=EOF) 31 { 32 memset(vis,0,sizeof(vis)); 33 memset(dp,0,sizeof(dp)); 34 memset(fa,0,sizeof(fa)); 35 for(i=1;i<=n;i++) 36 scanf("%d",&dp[i][1]); 37 while(scanf("%d%d",&a,&b)) 38 { 39 if(a==0&&b==0) 40 break; 41 fa[a]=b; //a的父节点是b 42 } 43 root=1; 44 while(fa[root]!=0) 45 root=fa[root]; 46 tree_dp(root); 47 cout<<max(dp[root][1],dp[root][0])<<endl;; 48 } 49 }
Anniversary party（POJ 2342 树形DP）
原文：http://www.cnblogs.com/a1225234/p/5225913.html