传送门啦
战略游戏这个题和保安站岗很像,这个题更简单,这个题求的是士兵人数,而保安站岗需要求最优价值。
定义状态$ f[u][0/1] $ 表示 $ u $ 这个节点不放/放士兵
根据题意,如果当前节点不放置士兵,那么它的子节点必须全部放置士兵,因为要满足士兵可以看到所有的边,所以
$ f[u][0]+=f[v][1] $ ,其中$ v $ 是 $ u $ 的子节点
如果当前节点放置士兵,它的子节点选不选已经不重要了(因为树形dp自下而上更新,上面的节点不需要考虑),所以
$ f[u][1]+=min(f[v][0],f[v][1]) $
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1505;
inline int read(){
char ch = getchar();
int f = 1 , x = 0;
while(ch > '9' || ch < '0'){if(ch == '-')f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}
return x * f;
}
int n,flag,k,x;
int head[maxn],tot;
int f[maxn][5];
struct Edge{
int from,to,next;
}edge[maxn << 1];
void add(int u,int v){
edge[++tot].from = u;
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot;
}
void dfs(int u,int fa) {
f[u][1] = 1 , f[u][0] = 0;
for(int i=head[u];i;i=edge[i].next) {
int v = edge[i].to;
if(v != fa) {
dfs(v , u);
f[u][0] += f[v][1];
f[u][1] += min(f[v][1] , f[v][0]);
}
}
}
int main(){
n = read();
for(int i=0;i<=n-1;i++){
flag = read(); k = read();
if(k == 0)continue;
for(int i=1;i<=k;i++){
x = read();
add(flag , x); add(x , flag);
}
}
dfs(0 , -1);
printf("%d\n",min(f[0][1] , f[0][0]));
return 0;
}
洛谷P2016战略游戏的更多相关文章
-
洛谷P2016 战略游戏
P2016 战略游戏 题目描述 Bob喜欢玩电脑游戏,特别是战略游戏.但是他经常无法找到快速玩过游戏的办法.现在他有个问题. 他要建立一个古城堡,城堡中的路形成一棵树.他要在这棵树的结点上放置最少数目 ...
-
[洛谷P2016] 战略游戏 (树形dp)
战略游戏 题目描述 Bob喜欢玩电脑游戏,特别是战略游戏.但是他经常无法找到快速玩过游戏的办法.现在他有个问题. 他要建立一个古城堡,城堡中的路形成一棵树.他要在这棵树的结点上放置最少数目的士兵,使得 ...
-
【洛谷P2016战略游戏】
树形dp的经典例题 题目描述 Bob喜欢玩电脑游戏,特别是战略游戏.但是他经常无法找到快速玩过游戏的办法.现在他有个问题. 他要建立一个古城堡,城堡中的路形成一棵树.他要在这棵树的结点上放置最少数目的 ...
-
洛谷 P2016 战略游戏
题意简述简述 求一棵树的最小点覆盖 题解思路 树形DP dp[i][0]表示第i个点覆盖以i为根的子树的最小值,且第i个点不放士兵 dp[i][1]表示第i个点覆盖以i为根的子树的最小值,且第i个点放 ...
-
$loj10156/$洛谷$2016$ 战略游戏 树形$DP$
洛谷loj Desription Bob 喜欢玩电脑游戏,特别是战略游戏.但是他经常无法找到快速玩过游戏的方法.现在他有个问题. 现在他有座古城堡,古城堡的路形成一棵树.他要在这棵树的节点上放置最少数 ...
-
洛谷 2016 战略游戏(树形DP)
题目描述 Bob喜欢玩电脑游戏,特别是战略游戏.但是他经常无法找到快速玩过游戏的办法.现在他有个问题. 他要建立一个古城堡,城堡中的路形成一棵树.他要在这棵树的结点上放置最少数目的士兵,使得这些士兵能 ...
-
洛谷2016 战略游戏 (0/1状态的普通树形Dp)
题意: 给出一个树,覆盖树上某一个点的花费为w[i],求树上每一条边至少有一个点覆盖的最小花费. 细节: 1.一条边的两端可以均被覆盖,但是不能存在一条边的两端都不被覆盖. 2.可能存在 分析: 对于 ...
-
洛谷 P2197 nim游戏
洛谷 P2197 nim游戏 题目描述 甲,乙两个人玩Nim取石子游戏. nim游戏的规则是这样的:地上有n堆石子(每堆石子数量小于10000),每人每次可从任意一堆石子里取出任意多枚石子扔掉,可以取 ...
-
洛谷 P1965 转圈游戏
洛谷 P1965 转圈游戏 传送门 思路 每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置,第 1 号位置小伙伴走到第 m+1 号位置,--,依此类推,第n − m号位置上的小伙伴走到第 0 号 ...
随机推荐
-
异步请求Ajax
AJAX:Asynchronous JS And XML,包括HTML.CSS.JS.DOM.XML.JSON等,客户端技术范畴.主要目标:发起异步请求/响应,实现页面内容的局部刷新,提高浏览体验:实 ...
-
ECC(Error Checking and Correction)校验和纠错
ECC的全称是 Error Checking and Correction or Error correction Coding,是一种用于差错检测和修正的算法.上一节的BBM中我们提到过,NAND闪 ...
-
Android菜鸟的成长笔记(8)——Intent与Intent Filter(上)
原文:[置顶] Android菜鸟的成长笔记(8)——Intent与Intent Filter(上) Intent代表了Android应用的启动“意图”,Android应用将会根据Intent来启动指 ...
-
phpmyadmin配置方式
简单的说,phpmyadmin就是一种mysql的管理工具,安装该工具后,即可以通过web形式直接管理mysql数据,而不需要通过执行系统命令来管理,非常适合对数据库操作命令不熟悉的数据库管理者,下面 ...
-
mybatis源码之StatementHandler
/** * @author Clinton Begin */ public interface StatementHandler { Statement prepare(Connection conn ...
-
Leetcode 88. Merge Sorted Array(easy)
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note:Yo ...
-
什么是url?
什么是URL? URL是统一资源定位器(Uniform Resource Locator)的缩写,也被称为网页地址,是因特网上标准的资源的地址. URL举例 http://www.sohu.com/s ...
-
windows错误:错误0x80070091 目录不是空的
错误: Window 下目录无法删除,提示 “ 错误0x80070091 目录不是空的 ” 解决: 1.开始菜单>附件>命令提示符>右键>以管理员身份运行 2.删除文件:(如 ...
-
C++中各种时间类型的转换(包括MFC中的时间类型)
平时写代码会经常遇到时间类型转换的问题,如时间戳转为格式化时间,或者反过来等,时间类型有的为time_t,还有FILETIME一堆,在这里记录下他们之间是如何转换的. 时间类型及其意义 FILETIM ...
-
【Java】使用BigDecimal类进行精确小数计算
在商业计算中(尤其是计算价格)需要使用BigDecimal类来进行精确小数计算,因为用其他类型计算(如double)得到的结果不是精确的! 写个测试类. import org.junit.Test; ...