本文主要是介绍hdu 1520 poj2342 anniversary party树形DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
每个节点要么选要么不选，和大多数选不选动归一样，来个dp[i][2]，0表示不选，1表示选，那我们只要从叶子节点往根结点不断更新dp[i][0]和dp[i][1]就可以了。状态转移方程:dp[i[[1] += dp[j][0] (当前选了，子节点必定不能选，然后累加)
dp[i][0] += max(dp[i][0],dp[i][1]) (当选不选，子节点可选可不选，找大的那个状态)
/*********************** Author:fisty* POJ2342* 树形DP* *******************/#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX_N 10000
int father[MAX_N],dp[MAX_N][MAX_N], vis[MAX_N];
int root,t;
int l,k;
void dfs(int root){vis[root] = 1;for(int i = 1;i <= t; i++){if(!vis[i] && father[i] == root){//节点没有被遍历并且i是root的儿子节点dfs(i);dp[root][1] += dp[i][0];dp[root][0] += max(dp[i][1], dp[i][0]);}}}
int main(){while(~scanf("%d", &t)){for(int i = 1;i <= t; i++){scanf("%d", &dp[i][1]);}while(scanf("%d%d", &l, &k) && l && k){father[l] = k; //l的父节点为kroot = k;}memset(vis, 0, sizeof(vis));dfs(root);printf("%d\n",max(dp[root][1], dp[root][0]));}return 0;
}
<pre name="code" class="cpp">/***************** Author:fisty* data:2014-12-7* hdu1520* 树形DP* ***************/#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=6050;
vector<int> T[MAXN];
int f[MAXN]; //f[i] = j 表示i的父亲是j,没有父节点值为-1
int a[MAXN];//每个节点的值
//dp[root][0] += max(dp[j][0],dp[j][1])
//dp[root][1] += dp[j][0];
int dp[MAXN][2]; void dfs(int root){dp[root][1] = a[root]; //选择根节点for(int i = 0;i < T[root].size(); i++){//对根节点进行深搜,从子叶往根进行遍历dfs(T[root][i]);} for(int i = 0;i < T[root].size(); i++){//遍历root的孩子节点int j = T[root][i];dp[root][0] += max(dp[j][0], dp[j][1]);dp[root][1] += dp[j][0];}}
int main(){int n;while(scanf("%d", &n) != EOF){for(int i = 1;i <= n; i++){scanf("%d", &a[i]); //输入每个节点的值T[i].clear();f[i] = -1; //每个点都没有父节点dp[i][0] = dp[i][1] = 0;} int a, b;//a 的上司为 bwhile(~scanf("%d%d", &a, &b)){if(!a && !b) break;f[a] = b;T[b].push_back(a);}a = 1;while(f[a] != -1) a = f[a]; //寻找根节点dfs(a);int ans = max(dp[a][1], dp[a][0]);printf("%d\n", ans);}return 0;
}
这篇关于hdu 1520 poj2342 anniversary party树形DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
