613. 火車站飯店

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

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

例如下圖是火車站網絡：

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

傳送門

那么，這是本蒟蒻做的第一道樹形DP。 樹形DP一般用搜索實現，先處理子節點，再處理自身，最終得到整棵樹的最優解，總是默認1為根節點。
本題中用dp[i][0]表示不選i節點時的最大獲利，dp[i][1]表示選擇i節點時的最大獲利。
#include<cstdio> #include<iostream> #include<algorithm> using namespace std;const int maxn = 100000 + 10; int G[maxn][51], value[maxn], dp[maxn][2], waynum[maxn]; bool vis[maxn][51]; int n;void Init(){scanf("%d",&n);for(int i = 1; i <= n; i++)scanf("%d",&value[i]);for(int i = 1; i <= n-1; i++){int x,y;scanf("%d%d",&x,&y);G[x][waynum[x]++] = y;G[y][waynum[y]++] = x;} } void DP(int pos){int temp(0), temp2(0);for(int i = 0; i < waynum[pos]; i++){if(!vis[pos][i]){for(int j = 0; j < waynum[G[pos][i]]; j++){if(G[G[pos][i]][j] == pos){vis[G[pos][i]][j] = 1;//標記是否訪問過break;}}DP(G[pos][i]);//與pos相連的某個節點(pos的兒子之一)temp2 += dp[G[pos][i]][0];//不選以pos為根的子樹temp += max(dp[G[pos][i]][1],dp[G[pos][i]][0]);//在選與不選中取較大的}}dp[pos][0] = temp;//不選pos節點dp[pos][1] = temp2 + value[pos];//選pos節點 } int main(){#ifndef DEBUGstring FileName="profitz";freopen((FileName+".in").c_str(),"r",stdin);freopen((FileName+".out").c_str(),"w",stdout);#endifInit();DP(1);printf("%d",max(dp[1][0],dp[1][1])); }

總結

以上是生活随笔為你收集整理的COGS 613. 火车站饭店 解题报告的全部內容，希望文章能夠幫你解決所遇到的問題。

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