本文主要是介绍UVa 1292 - Strategic game (树形dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本文出自 http://blog.csdn.net/shuangde800
题目链接： 点击打开链接
题目大意
给定一棵树，选择尽量少的节点，使得每个没有选中的结点至少和一个已选结点相邻。
思路
经典的树形dp题，据说是最小顶点覆盖。
f[u][0]: 表示不选i点，覆盖这个子树的最少点
f[u][1]：选i点，覆盖这个子树的最少点
对于u点，如果选择这个点，那么他的字节点可选也可不选
如果不选u点的话，那么它的子结点就必须要选！开始时我以为字节点只要至少选一个就可以了，但是这样是错的！
因为会出现下面这种情况：
顶点1不选，子节点中2有选了，但是3却没有相邻结点有选。
所以可以得到状态转移方程：
f[u][1] = sum{ min{f[v][0], f[v][1]}, v是u的子结点 }
f[u][0] = sum{ f[v][1], v是u的子结点 }
代码
/**==========================================
* This is a solution for ACM/ICPC problem
*
* @problem: UVA 1292 - Strategic game
* @type: dp
* @author: shuangde
* @blog: blog.csdn.net/shuangde800
* @email: zengshuangde@gmail.com
*===========================================*/
#include#include#include#include#include#include #include using namespace std; typedef long long int64; const int INF = 0x3f3f3f3f; const double PI = acos(-1.0); const int MAXN = 1510; int n; int f[MAXN][2]; bool vis[MAXN]; vector adj[MAXN]; void dfs(int u){ vis[u] = true; f[u][0] = 0; f[u][1] = 1; for(int i=0; i
这篇关于UVa 1292 - Strategic game (树形dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
