POJ-2342 Anniversary party(Tree dp)

发布时间:2016-12-8 8:16:03 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"POJ-2342 Anniversary party(Tree dp)",主要涉及到POJ-2342 Anniversary party(Tree dp)方面的内容,对于POJ-2342 Anniversary party(Tree dp)感兴趣的同学可以参考一下。

最基础的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); } }

上一篇:【PHPWord】创建带样式表格的Word文档
下一篇:黑马程序员————高新技术————JDK1.5新特性

相关文章

相关评论