hdoj 1520 Anniversary party(樹形dp)

   按照等級我們可以建一顆樹，如圖

      我們可以把一個節點當做一個人，每個節點都有一個權重。按照題目意思，如果我們取了某個節點，那麼他的父節點和子節點都是不能取的。按要求選取節點，使得選取節點的權重和最大。

     DP,用no表示不選擇i點時，i點及其子樹能選出的最多人數，is表示選擇i點時，i點及其子樹的權值和最大。

狀態轉移方程:

—對於葉子節點 dp[k].no = 0, dp[k].no = a[k].v
—對於非葉子節點i,
—dp[i].no = ∑max(dp[j][0], dp[j][1]) (j是i的兒子)
—dp[i].is = v + ∑dp[j].no (j是i的兒子)

代碼：

[cpp]
#include <stdio.h>  
#include <algorithm>  
#include <vector>  
#include <string.h>  
using namespace std; 
 
struct node 
{ 
    int v; 
    int is, no; 
    vector<int> son; 
}a[6010]; 
 
bool f[6010]; 
 
void dp(int x) 
{ 
    int t; 
    for (unsigned int i = 0; i < a[x].son.size(); i++) 
    { 
        t = a[x].son[i]; 
        dp(t); 
        a[x].is += a[t].no; 
        a[x].no += max(a[t].no, a[t].is); 
    } 
} 
 
int main() 
{ 
    int n; 
    while (scanf("%d", &n) != EOF) 
    { 
        for (int i = 1; i <= n; i++) 
        { 
            scanf("%d", &a[i].v); 
            a[i].son.clear(); 
            a[i].is = a[i].v; 
            a[i].no = 0; 
        } 
        int son, fa; 
        memset(f, 0, sizeof(f)); 
        while (scanf("%d %d",&son, &fa) && son+fa) 
        { 
            a[fa].son.push_back(son); 
            f[son] = 1; 
        } 
        for (int i = 1; i <= n; i++) 
        { 
            if (f[i] == false) 
            { 
                dp(i); 
                printf("%d\n",max(a[i].is, a[i].no)); 
                break; 
            } 
        } 
    } 
    return 0; 
} 

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;

struct node
{
    int v;
    int is, no;
    vector<int> son;
}a[6010];

bool f[6010];

void dp(int x)
{
    int t;
    for (unsigned int i = 0; i < a[x].son.size(); i++)
    {
        t = a[x].son[i];
        dp(t);
        a[x].is += a[t].no;
        a[x].no += max(a[t].no, a[t].is);
    }
}

int main()
{
    int n;
    while (scanf("%d", &n) != EOF)
    {
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i].v);
            a[i].son.clear();
            a[i].is = a[i].v;
            a[i].no = 0;
        }
        int son, fa;
        memset(f, 0, sizeof(f));
        while (scanf("%d %d",&son, &fa) && son+fa)
        {
            a[fa].son.push_back(son);
            f[son] = 1;
        }
        for (int i = 1; i <= n; i++)
        {
            if (f[i] == false)
            {
                dp(i);
                printf("%d\n",max(a[i].is, a[i].no));
                break;
            }
        }
    }
    return 0;
}