POJ 2342 简单树形dp

Description

Input

Output

Sample Input

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0

Sample Output

5

子节点与父节点不能同时选，求权值，简单树形dp

dp[u][0]表示当前节点不选，dp[u][1]表示当前节点选。

状态方程：dp[u][0]+=max(dp[v][0],dp[v][1])表示当前节点不选时叠加子节点选与不选的最大值。

                    dp[u][1]+=dp[v][0]，表示当前节点选时，子节点不选。

代码：

/* ***********************************************
Author :xianxingwuguan
Created Time :2014-2-6 3:11:18
File Name :3.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=10001;
int head[maxn],weight[maxn],dp[maxn][2],tol;
struct node{
	int next,to;
}edge[2*maxn];
void add(int u,int v){
	edge[tol].to=v;
	edge[tol].next=head[u];
	head[u]=tol++;
}
void dfs(int u,int fa){
	dp[u][1]=weight[u];
    for(int i=head[u];i!=-1;i=edge[i].next){
	    int v=edge[i].to;
		if(v==fa)continue;
		dfs(v,u);
		dp[u][1]+=dp[v][0];
		dp[u][0]+=max(dp[v][1],dp[v][0]);
	}
}
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     int i,j,k,m,n;
	 while(~scanf("%d",&n)){
		 memset(head,-1,sizeof(head));tol=0;
		 memset(dp,0,sizeof(dp));
		 for(i=1;i<=n;i++)
			 scanf("%d",&weight[i]);
		 while(~scanf("%d%d",&i,&j)&&i&&j){
			 add(i,j);
			 add(j,i);
		 }
		 dfs(1,-1);
		 //cout<<"hahha"<<endl;
		 printf("%d\n",max(dp[1][0],dp[1][1]));
	 }
     return 0;
}

POJ 2342 简单树形dp

原文：http://blog.csdn.net/xianxingwuguan1/article/details/18945153