POJ2342：
题意：某公司要举办一次晚会，但是为了使得晚会的气氛更加活跃，每个参加晚会的人都不希望在晚会中见到他的直接上司，现在已知每个人的活跃指数和上司关系（当然不可能存在环），求邀请哪些人（多少人）来能使得晚会的总活跃指数最大。
题解：
当i来的时候，dp[i][1] += dp[j][0];//j为i的下属
当i不来的时候，dp[i][0] +=max(dp[j][1],dp[j][0]);//j为i的下属
#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <queue> #include <typeinfo> #include <map> //#include<bits/stdc++.h> typedef long long ll; using namespace std; #define inf 10000000 inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘)f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=x*10+ch-‘0‘; ch=getchar(); } return x*f; } //*************************************************************** int dp[10000][2]; int vis[10000]; int parent[10000]; int n,a,b; void sp(int x) { vis[x]=1; for(int i=1;i<=n;i++) { if(parent[i]==x&&!vis[i]) { sp(i); dp[x][0]+=max(dp[i][0],dp[i][1]); dp[x][1]+=dp[i][0]; } } } int main() { while(cin>>n) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) scanf("%d",&dp[i][1]); memset(vis,0,sizeof(vis)); int root=0; memset(parent,0,sizeof(parent)); while(scanf("%d%d",&a,&b)&&a&&b) { parent[a]=b; root=b; } sp(root); printf("%d\n",max(dp[root][0],dp[root][1])); } return 0; }
原文：http://www.cnblogs.com/zxhl/p/4744769.html
