poj 2342 樹形DP

樹形DP入門題目。

樹形DP說白了就是在搜索的時候動態規劃。

只要你懂的深搜+動態規劃，就能理解這個基礎題了。

先直接搜索到最底層，然後一層一層動態規劃，可以說有點像數塔。

dp[i][1],dp[i][0]代表取這個節點和不取這個節點，所以。

dp[i][1]+=dp[v][0] v是的子節點

dp[i][0]+=max(dp[v][1],dp[v][0])

初始的時候將最後一層葉子節點dp[i][1]賦值為相應值即可。

用鄰接表 似乎更加的直觀，速度自然是更加的快。

#include
#include
#include
using namespace std;
struct node{
	int v,nxt;
}e[12000];
int dp[6005][2],father[6005];
int num,head[6005];

int max(int a,int b){
	return a>b?a:b;
}	
void add(int a,int b){
	e[num].v=b;e[num].nxt=head[a];head[a]=num++;
}		


void dfs(int n){
	int i;
	for(i=head[n];i!=-1;i=e[i].nxt){
		int v=e[i].v;
		if(father[v]==n){
			dfs(v);
			dp[n][1]+=dp[v][0];
			dp[n][0]+=max(dp[v][1],dp[v][0]);
		}
	}	
}	
int main()
{
	int t;
	while(scanf("%d",&t)!=EOF){
		memset(dp,0,sizeof(dp));
		memset(head,-1,sizeof(head));
		memset(father,0,sizeof(father));
		num=0;
		int i;
		for(i=1;i<=t;i++)
			scanf("%d",&dp[i][1]);
		int root=1;
		int a,b;
		while(scanf("%d%d",&a,&b),a||b){
			father[a]=b;
			add(b,a);
			if(father[b]==0) root=b;
		}
		dfs(root);
		printf("%d\n",dp[root][1]>dp[root][0]?dp[root][1]:dp[root][0]);
	}
	return 0;
}