題目描述

Bob喜歡玩電腦游戲，特別是戰略游戲。但是他經常無法找到快速玩過游戲的辦法。現在他有個問題。

他要建立一個古城堡，城堡中的路形成一棵樹。他要在這棵樹的結點上放置最少數目的士兵，使得這些士兵能了望到所有的路。

注意，某個士兵在一個結點上時，與該結點相連的所有邊將都可以被了望到。

請你編一程序，給定一樹，幫Bob計算出他需要放置最少的士兵.

輸入格式

第一行 N，表示樹中結點的數目。

第二行至第N+1行，每行描述每個結點信息，依次為：該結點標號i，k(后面有k條邊與結點I相連)。

接下來k個數，分別是每條邊的另一個結點標號r1，r2，...，rk。

對于一個n(0<n<=1500)個結點的樹，結點標號在0到n-1之間，在輸入數據中每條邊只出現一次。

輸出格式

輸出文件僅包含一個數，為所求的最少的士兵數目。

例如，對于如下圖所示的樹：

2 / 0---1\3

答案為1（只要一個士兵在結點1上）。

輸入輸出樣例

輸入 #1復制

4 0 1 1 1 2 2 3 2 0 3 0

輸出 #1復制

1

【分析】

題目相當于需要求覆蓋這顆樹需要的最小點數

用???表示在這棵樹中，以?ii?為根節點的子樹在選/不選根節點的情況下，覆蓋這棵樹所有邊需要的最小點數

所以，當不選這個節點?ii?時，則所有 以其子節點為根節點的子樹 都必選根節點

當選擇這個節點?ii?時，它能連接到所有的子節點，所以 以其子節點為根節點的子樹 可以選則其根節點，也可以不選

歸納成方程組，可能更容易理解：

其中，Son_iSoni??為?ii?的子節點集合

顯然，邊界為

如果定義?時

遞推式及其邊界便能寫在一起了：

答案看了以上大牛的解析

#include<iostream> #include<algorithm> #include<queue> #include<cstring> using namespace std; vector <int> edge[1510]; int dp[2][1510],n,x,y,sum[1510],z; void solve(int u,int fa) {for(int i=0;i<edge[u].size();i++){int v=edge[u][i];if(v==fa)continue;solve(v,u);dp[0][u]+=dp[1][v];dp[1][u]+=min(dp[1][v],dp[0][v]);}dp[1][u]++; } int main() {cin>>n;for(int i=1;i<=n;i++){cin>>x>>sum[x];for(int i=1;i<=sum[x];i++){cin>>z;edge[x].push_back(z);edge[z].push_back(x);}}solve(0,0);int ans=min(dp[0][0],dp[1][0]);cout<<ans;return 0; }

?

總結

以上是生活随笔為你收集整理的洛谷 2016 战略游戏（树形DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

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