什么是樹形DP呢？看完這個入門題目，估計你就明白了！
HDU1520-Anniversary party 題目描述：人們都不愿意在聚會中遇到自己的直接上司。現在給出每個人能帶給聚會的歡樂值以及他們直接的上司下屬關系，問聚會歡樂值最高可以是多少？ 輸入輸出：參見評測網站題目。
對于這道題，我們可以先使用鄰接表存儲某人和他的直接下屬。因為我們知道：如果某人去參加聚會，那么他的直接下屬就一定不能參加；如果某人不去參加聚會，那么他的直接下屬可以選擇參加或不參加。 所以對于dp數組和狀態轉移方程有： dp[i][0]表示編號為i的人不去聚會； dp[i][1]表示編號為i的人去聚會。 dp[i][0]+=max{dp[i的直接下屬][0],dp[i的直接下屬][1]}; dp[i][1]+=dp[i的直接下屬][0]; dp[i][1]還要加上v[i]，也就是他的歡樂值，別忘了他自己！
#include<cstdio>#include<cstring>#define N 6005struct node{ int from,to,next;}edge[2*N];int head[N],tol,visit[N],val[N],degree[N],dp[N][3];void add(int a,int b)//鄰接表存儲 { tol++; edge[tol].from=a; edge[tol].to=b; edge[tol].next=head[a]; head[a]=tol;}int max(int a,int b){ return a>b?a:b;}void dfs(int root){ int j,u,ans1,ans0; visit[root]=1; ans1=ans0=0; for(j=head[root];j!=-1;j=edge[j].next)//對于某人的所有直接下屬進行討論 { u=edge[j].to; if(!visit[u])dfs(u); ans0+=max(dp[u][0],dp[u][1]);//對于某人不去，直接下屬可選擇去或不去 ans1+=dp[u][0];//對于某人去，直接下屬只能不去 } dp[root][1]=ans1+val[root]; dp[root][0]=ans0;}int main(){ int i,n,sum,a,b; while(scanf("%d",&n)!=EOF) { for(i=1;i<=n;i++) scanf("%d",&val[i]); memset(head,-1,sizeof(head)); memset(degree,0,sizeof(degree)); tol=0; while(scanf("%d%d",&a,&b)!=EOF) { if(a==0 && b==0) break; add(b,a); degree[a]++; } memset(visit,0,sizeof(visit)); memset(dp,0,sizeof(dp)); sum=0; for(i=1;i<=n;i++) { if(degree[i]==0)//如果某人再沒有直接上司（說明他是根節點）。 //注意：可能有多個根節點！！！ { dfs(i); sum+=max(dp[i][0],dp[i][1]); } }新聞熱點
疑難解答
