[動態規劃]NOIP模擬題 ：火車站飯店（最大利潤） profitz 解題報告

【題目描述】

政府邀請了你在火車站開飯店，但不允許同時在兩個相連的火車站開。任意兩個火車站有且只有一條路徑，每個火車站最多有 50 個和它相連接的火車站。

告訴你每個火車站的利潤，問你可以獲得的最大利潤爲多少？

例如下圖是火車站網絡：

最佳投資方案是 1 ， 2 ， 5 ， 6 這 4 個火車站開飯店可以獲得的利潤爲 90.

【輸入格式】

第一行輸入整數 N(<=100000), 表示有 N 個火車站，分別用 1,2,……..,N 來編號。接下來 N 行，每行一個整數表示每個站點的利潤，接下來 N-1 行描述火車站網絡，每行兩個整數，表示相連接的兩個站點。

【輸出格式】

輸出一個整數表示可以獲得的最大利潤。

【樣例輸入】

6

10

20

25

40

30

30

4 5

4 6

3 4

1 3

2 3

【樣例輸出】

90

【分析】

簡單的樹形動態規劃，直接遞歸找最優子問題即可。

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

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

狀態轉移方程：

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

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

我同學Paulinsider的解題報告：傳送門

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
#define max(a,b) a>b?a:b
using namespace std;
const int MAXN=100001;
int N; //N個火車站
int Mat[MAXN][51]; //記錄每個節點與哪些節點相鄰
int Profit[MAXN]; //每個節點的權值（利潤）
int Abut[MAXN]={0};  //記錄與每個節點相鄰的節點的個數
int F[MAXN][2]; //F[i][0]不選i號節點的最大利潤 , F[i][1]選第i號節點的最大利潤
bool used[MAXN]={0};//記錄每個節點是否被用過

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

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

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