hdu 1054 Strategic Game 树状DP

本文主要是介绍hdu 1054 Strategic Game 树状DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门：hdu 1054 Strategic Game

题目大意

一城堡的所有的道路形成一个n个节点的树，如果在一个节点上放上一个士兵，那么和这个节点相连的边就会被看守住，问把所有边看守住最少需要放多少士兵。

解题思路

这是个典型的树形DP的题目！
1．根—>叶：既根传递有用的信息给子节点，完后根得出最优解的过程。
2．叶－>根：既根的子节点传递有用的信息给根，完后根得出最优解的过程。这类的习题比较的多，应用比较广泛!
当然还有一种比较少见的，同时需要两种遍历方向！
这个题目就是属于第二种情况。
首先我们需要明确状态：
dp[i][j]表示第i个节点是选或者不选（j还有0或者1，0代表不选，1代表选）造成需要放的最小士兵的数量！
状态转移方程为：dp[i][k] = {sum(min(dp[j][0],dp[j][1])),j是i的孩子}

由于输入的是一个无根树我们需要把这个无根树变为有根树，只需要增加一个数组pre[i]代表i的父亲是谁，初始化时候pre[i] = i；只需要选定一个为根就可以了！因为是个树状的结构所以递归是最好的方式了。
就好像下面的这个图

其中c7是根节点！
不要以为以为第i个节点如果选了的话，那么他的孩子就一定不选，因为那种情况不一定是最好的选择，就像c5如果选了c5的话，并且选了c11才是最好的选择!

AC代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN =  1500 + 15;
int size[MAXN],dp[MAXN][5],son[MAXN][MAXN],pre[MAXN];int dfs(int pos,int val)
{if(dp[pos][val]!=1) return dp[pos][val];int sum = val;for(int i=0;i<size[pos];i++){if(val) sum+=min(dfs(son[pos][i],0),dfs(son[pos][i],1));else sum+=dfs(son[pos][i],1);}return dp[pos][val] = sum;
}
int main()
{int N,X,M;while(~scanf("%d",&N)){for(int i=0;i<N;i++){pre[i] = i;dp[i][0] = 1;dp[i][1] = 1;}for(int i=0;i<N;i++){scanf("%d:(%d)",&X,&M);size[X] = M;for(int j=0;j<M;j++){scanf("%d",&son[X][j]);pre[son[X][j]] = X;}}int ans;for(int i=0;i<N;i++)if(pre[i] == i) {ans = min(dfs(i,0),dfs(i,1));break;}printf("%d\n",ans);}return 0;
}