原题链接:http://poj.org/problem?id=2342
题意:某公司要举办一次晚会,但是为了使得晚会的气氛更加活跃,每个参加晚会的人都不希望在晚会中见到他的直接上司,现在已知每个人的活跃指数和上司关系(当然不可能存在环),求邀请哪些人(多少人)来能使得晚会的总活跃指数最大。
分析:任何一个点的取舍可以看作一种决策,那么状态就是在某个点取的时候或者不取的时候,以他为根的子树能有的最大活跃总值。分别可以用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的下属
#define _CRT_SECURE_NO_DEPRECATE #include<iostream> #include<vector> #include<cstring> #include<queue> #include<stack> #include<algorithm> #include<cmath> #include<string> #include<stdio.h> #define INF 99999999 #define eps 0.0001 using namespace std; int n; int root; int dp[6005][2];//dp[i][0]0表示不去,dp[i][1]1表示去了 int father[6005]; void tree_dp(int node) { for (int i = 1; i <= n; i++) { if (father[i] == node) { tree_dp(i); dp[node][1] += dp[i][0]; dp[node][0] += max(dp[i][0], dp[i][1]); } } } int main() { while (~scanf("%d", &n)) { memset(father, 0, sizeof(father)); for (int i = 1; i <= n; i++) scanf("%d", &dp[i][1]); int d, u; while (scanf("%d %d", &d, &u) && (d || u)) father[d] = u; root = 1; while (father[root]) root = father[root]; tree_dp(root); printf("%d\n", max(dp[root][0], dp[root][1])); } return 0; }