一道還算比較好寫的“求樹的最大獨立集”的問題。

　　f [ x ] [ 0 ] 表示以x為節(jié)點的子樹上，在x位置不放士兵時，士兵數(shù)量的最小值；

　　f [ x ] [ 1 ] 表示以x為節(jié)點的子樹上，在x位置要放士兵時，士兵數(shù)量的最小值；

　　那么方程就寫出來了，在回溯的時候，對于f [ x ] [ 0 ] ，它的子節(jié)點一定都要放，累加f [ x ] [ 1 ] ；那么對于f [ x ] [ 1 ] ，取最小值就可以了。??

　　注意邊界判斷，當(dāng)你到樹的葉子的時候，要在操作 f 之后返回。

　　代碼如下：

　

#include<cstdio> #include<iostream> #include<cstring> using namespace std; #define maxn 2000 struct data {int num,child[maxn]; } node[maxn]; int f[maxn][3],n,root; bool vis[maxn]; void dp(int x) {f[x][0]=0;f[x][1]=1;if(!node[x].num) return ;for(int i=1;i<=node[x].num;i++){dp(node[x].child[i]);f[x][0]+=f[node[x].child[i]][1];f[x][1]+=min(f[node[x].child[i]][1],f[node[x].child[i]][0]);} } int main() {memset(f,0x3f,sizeof(f));scanf("%d",&n); for(int i=1;i<=n;i++){int x,y;scanf("%d",&x);scanf("%d",&node[x].num);for(int j=1;j<=node[x].num;j++){scanf("%d",&node[x].child[j]);vis[j]=1;}}while(vis[root]) root++;dp(root);printf("%d",min(f[root][0],f[root][1]));return 0; }

?　　最后想加一句，所謂樹形dp，我認(rèn)為就是想方設(shè)法利用剛剛到過（并從那里回來）的點更新現(xiàn)在這個點，更新到最后就是答案了。

轉(zhuǎn)載于:https://www.cnblogs.com/popo-black-cat/p/10182644.html

總結(jié)

以上是生活随笔為你收集整理的P2016 战略游戏的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。