POJ-2342 Anniversary party(Tree dp)

发布时间:2014-10-22 13:59:44
来源:分享查询网

最基础的Tree dp dp[i][0]表示编号为i的结点不去,dp[i][1]表示编号为i的结点去。 转移方程为dp[i][0] += max(dp[son[i]][0],dp[son[i]][1]);                     dp[i][1] += dp[son[i]][0]; #include <stdio.h> #include <malloc.h> #include <stdlib.h> #include <string.h> const int MAXN = 6005; int n; int dp[MAXN][2],fa[MAXN]; bool vis[MAXN]; inline int max(int a,int b){ return a<b ? b : a; } void dfs(int root) { vis[root] = 1; for(int i = 1;i <= n;i++) { if(!vis[i]&&fa[i]==root) { dfs(i); dp[root][1] += dp[i][0]; dp[root][0] += max(dp[i][0],dp[i][1]); } } } int main() { while(scanf("%d",&n) != EOF) { memset(dp,0,sizeof(dp)); memset(vis,0,sizeof(vis)); memset(fa,0,sizeof(fa)); for(int i = 1;i <= n;i++) scanf("%d",&dp[i][1]); bool beg = 1; int root = 0,l,k; while(scanf("%d%d",&l,&k) == 2 && l+k>0){ fa[l] = k; if(root==l||beg) { root = k; beg = 0; } } dfs(root); printf("%d\n",max(dp[root][0],dp[root][1])); //Free(n); } }

返回顶部
查看电脑版