樹形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<cstdio> #include<cstring> #include<iostream> 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; }

總結

以上是生活随笔為你收集整理的poj 2342 树形DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。