首页 > Strategic game
开通博客写题解
头像 回归梦想
发表于 2020-08-26 17:55:32
来源：牛客网： 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 10000K，其他语言20000K 64bit IO Format: %lld 题目描述 Bob enjoys playing computer games, especially strategic games, bu 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 瑜画
发表于 2020-08-08 09:53:22
本题是树的最小点覆盖问题。设想一个结点放士兵和不放士兵两种情况，如果放士兵，那它的孩子们放不放士兵都无所谓，如果不放士兵，那孩子们必须放士兵（否则将无法覆盖） 那么很容易想到状态转移方程：dp[root][1]=1+ min(dp[son][1],dp[son][0])dp[root][0]= dp 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Ray.C.L
发表于 2020-08-10 13:47:27
题意： 一城堡的所有的道路形成一个n个节点的树，如果在一个节点上放上一个士兵，那么和这个节 点相连的边就会被看守住，问把所有边看守住最少需要放多少士兵。 思路：用dp[i][0]表示以i为根节点，但是i节点不放士兵需要看守的最少士兵是多少,dp[i][1]表示以i为根节点，i节点放置守卫时所需的最少 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”