Anniversary party POJ - 2342 （树形DP）
题目链接：
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。题目大意：给你n个人，然后每个人的重要性，以及两个人之间的附属关系，当上属选择的时候，他的下属不能选择，只要是两个人不互相冲突即可。然后问你以最高领导为起始点的关系网的重要性最大。
具体思路：简单树形DP，
dp[i][0]表示当前i点不选择，那么dp[i][0] = sum( max(dp[to][1] ,dp[to][0] ) )(to为i的子节点)。
dp[i][1]表示当前i点选择， 那么dp[i][1] = dp[i][1] + sum(dp[to][0])(to为i的子节点)。
反思：可能会有多个起点的情况
AC代码：
1 #include<iostream> 2 #include<stdio.h> 3 #include<cmath> 4 #include<vector> 5 #include<cstring> 6 #include<string> 7 using namespace std; 8 # define ll long long 9 # define inf 0x3f3f3f3f 10 const int maxn = 2e5+100; 11 int dp[maxn][2]; 12 int in[maxn]; 13 vector <int> Edge[maxn]; 14 int vis[maxn]; 15 void dfs(int u) 16 { 17 vis[u]=1; 18 for(int i=0; i<Edge[u].size(); i++) 19 { 20 int to=Edge[u][i]; 21 if(vis[to]) 22 continue; 23 dfs(to); 24 dp[u][1]=dp[u][1]+dp[to][0]; 25 dp[u][0]=dp[u][0]+max(dp[to][0],dp[to][1]); 26 } 27 } 28 int main ( ) 29 { 30 int n; 31 scanf("%d", &n); 32 for(int i=1 ; i <=n ; i++ ) 33 { 34 scanf("%d", &dp[i][1] ); 35 } 36 int st,ed; 37 while(~scanf("%d %d",&st,&ed)&&(st+ed)) 38 { 39 Edge[ed].push_back(st); 40 in[st]++; 41 } 42 int root; 43 for(int i=1; i<=n; i++) 44 { 45 if(!in[i]) 46 { 47 root=i; 48 dfs(root); 49 break; 50 } 51 } 52 printf("%d\n",max(dp[root][0],dp[root][1])); 53 return 0; 54 }
更多精彩
