| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 3863 | Accepted: 2172 |
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
题意：有一个大学的庆典晚会，想邀请一些在大学任职的人来参加，每个人有自己的搞笑值，但是现在遇到一个问题就是如果两个人之间有直接的上下级关系，那么他们中只能有一个来参加，求请来一部分人之后，搞笑值的最大是多少
思路：树形DP，在整个树上跑一遍dfs，设dp[s][0]表示不取s时以s为跟节点的子树的最大搞笑值，dp[s][1]表示取s时以s为跟节点的子树的最大搞笑值，则状态转移方程为:
dp[s][0] += max(dp[u][0], dp[u][1]);
dp[s][1] += dp[u][0];
1 #include<cstdio> 2 #include<string> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #define MAXN 6010 7 using namespace std; 8 int dp[MAXN][2], rat[MAXN]; 9 int vis[MAXN], head[MAXN]; 10 typedef struct{ 11 int to, next; 12 }Edge; 13 Edge edge[MAXN]; 14 void addedge(int u, int v, int k){ 15 edge[k].to = v; 16 edge[k].next = head[u]; 17 head[u] = k; 18 } 19 void dfs(int s){ 20 dp[s][0] = 0; 21 dp[s][1] = rat[s]; 22 for(int i = head[s];~i;i = edge[i].next){ 23 int u = edge[i].to; 24 dfs(u); 25 dp[s][0] += max(dp[u][0], dp[u][1]); 26 dp[s][1] += dp[u][0]; 27 } 28 } 29 int main(){ 30 int n, u, v, father; 31 freopen("in.c", "r", stdin); 32 while(~scanf("%d", &n)){ 33 memset(vis, 0, sizeof(vis)); 34 memset(head, -1, sizeof(head)); 35 for(int i = 1;i <= n;i ++) scanf("%d", rat+i); 36 for(int i = 1;i <= n-1;i ++){ 37 scanf("%d%d", &u, &v); 38 addedge(v, u, i); 39 vis[u] = 1; 40 } 41 scanf("%d%d", &u, &v); 42 for(int i = 1;i <= n;i ++){ 43 if(!vis[i]){ 44 father = i; 45 break; 46 } 47 } 48 dfs(father); 49 printf("%d\n", max(dp[father][0], dp[father][1])); 50 } 51 return 0; 52 }
POJ 2342 （树形DP）,布布扣,bubuko.com
原文：http://www.cnblogs.com/anhuizhiye/p/3702661.html