首页 > 代码库 > hdu - 1054 - Strategic Game(树形dp)
hdu - 1054 - Strategic Game(树形dp)
题意:一棵n个结点的无根树(0 < n <= 1500),在一个结点放一个士兵,可以守护与这个点相邻的所有边,问最少需要多少个士兵,可以守护所有边。
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1054
——>>状态:
dp[i][1]表示以 i 为结点的子树,在 i 放一个士兵,可以守护所有边的最少士兵数。
dp[i][0]表示以 i 为结点的子树,在 i 不放士兵,可以守护所有边的最少士兵数。
状态转移方程(结点 j 是结点 i 的儿子):
dp[i][1] += min(dp[j][1], dp[j][0]);(如果结点 i 放了士兵,那么 i 连向其儿子的边已被守护,所以其儿子可放可不放士兵)
dp[i][0] += dp[j][1];(如果结点 i 不放士兵,那么 i 连向其儿子的边必须由其儿子守护)
对于叶子结点i:
dp[i][1] = 1;(虽然以叶子为根的子树无边,但因放了一个士兵在根,所以是1)
dp[i][0] = 0;
#include <cstdio> #include <cstring> #include <algorithm> using std::min; const int MAXN = 1500 + 10; struct EDGE { int nTo; int nNext; }; int nHead[MAXN]; int nEdge; int dp[MAXN][2]; EDGE edge[MAXN << 1]; void Init() { nEdge = 0; memset(nHead, -1, sizeof(nHead)); } void AddEdge(int nFrom, int nTo) { edge[nEdge].nTo = nTo; edge[nEdge].nNext = nHead[nFrom]; nHead[nFrom] = nEdge++; } void Read(int n) { int nFrom; int nCnt; int nTo; for (int i = 0; i < n; ++i) { scanf("%d:(%d)", &nFrom, &nCnt); for (int j = 0; j < nCnt; ++j) { scanf("%d", &nTo); AddEdge(nFrom, nTo); AddEdge(nTo, nFrom); } } } void Dfs(int i, int nFather) { dp[i][1] = 1; dp[i][0] = 0; if (nHead[i] == -1) return; for (int e = nHead[i]; e != -1; e = edge[e].nNext) { int j = edge[e].nTo; if (j != nFather) { Dfs(j, i); dp[i][1] += min(dp[j][1], dp[j][0]); dp[i][0] += dp[j][1]; } } } void Output() { printf("%d\n", min(dp[0][1], dp[0][0])); } int main() { int n; while (scanf("%d", &n) == 1) { Init(); Read(n); Dfs(0, -1); Output(); } return 0; }
hdu - 1054 - Strategic Game(树形dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。