[動態規劃]USACO Nov10 拜訪奶牛 vacation 解題報告

【題目描述】
經過了幾周的辛苦工作,貝茜終於迎來了一個假期.作爲奶牛羣中最會社交的牛,她希望去拜訪N(1<=N<=50000)個朋友.這些朋友被標號爲1..N.這些奶牛有一個不同尋常的交通系統,裏面有N-1條路,每條路連接了一對編號爲C1和C2的奶牛(1 <= C1 <= N; 1 <= C2 <= N; C1<>C2).這樣,在每一對奶牛之間都有一條唯一的通路.

FJ希望貝茜儘快的回到農場.於是,他就指示貝茜,如果對於一條路直接相連的兩個奶牛,貝茜只能拜訪其中的一個.當然,貝茜希望她的假期越長越好,所以她想知道她可以拜訪的奶牛的最大數目.

輸入格式:

第1行:單獨的一個整數N

第2..N行:每一行兩個整數,代表了一條路的C1和C2.

樣例輸入(vacation.in):

7

6 2

3 4

2 3

1 2

7 6

5 6

輸入說明:

貝茜認識7只奶牛,其中6和2相連,3和4相連,等等...最後形成這麼一個網絡:

1--2--3--4

      |

5--6--7

輸出格式:

第一行:單獨的一個整數,代表了貝茜可以拜訪的奶牛的最大數目.

樣例輸出(vacation.out):

4

輸出解釋:

{1,3,5,7}或{1,4,5,7}或{2,4,5,7}

【數據範圍】

40%數據 n<=100

100%數據 n<=50000

【分析】

經典的樹形DP，直接遞歸找最優子狀態即可。

F[i][0] :不選第i個節點 的最大利潤。

F[i][1] :選第i個節點 的最大利潤。

邊界條件：F[i][1=1;

狀態轉移方程：

F[i][0]+=max{ F[x][0] ,  F[x][1] } (i與x鄰接)

F[i][1]+=F[x][0] (x與i鄰接)


【我的代碼】
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
const int MAXN=50001;
int F[MAXN][2];
int Mat[MAXN][10];
int Abut[MAXN]={0};
bool used[MAXN]={0};
int N;

void init()
{
    scanf("%d\n",&N);
   
    for (int i=1;i<=N;i++)
        F[i][1]=1;
   
    int a,b;
    for (int i=1;i<=N-1;i++)
    {
        scanf("%d %d\n",&a,&b);
        Abut[a]++;
        Abut[b]++;
        Mat[a][Abut[a]]=b;
        Mat[b][Abut[b]]=a;
    }
    return;
}

int max(int a,int b)
{
    return a>b?a:b;
}

void dp(int x)
{
    used[x]=true;
    for (int i=1;i<=Abut[x];i++)
    {
        if(used[Mat[x][i]])
            continue;
        dp(Mat[x][i]);
        F[x][1]+=F[Mat[x][i]][0];
        F[x][0]+=max(F[Mat[x][i]][0],F[Mat[x][i]][1]);
    }
}

int main()
{
    freopen("vacation.in","r",stdin);
    freopen("vacation.out","w",stdout);
    init();
    dp(1);
    printf("%d\n",max(F[1][0],F[1][1]));
    return 0;
}