Desription
Bob 喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的方法。现在他有个问题。
现在他有座古城堡，古城堡的路形成一棵树。他要在这棵树的节点上放置最少数目的士兵，使得这些士兵能够瞭望到所有的路。
注意：某个士兵在一个节点上时，与该节点相连的所有边都将能被瞭望到。
请你编一个程序，给定一棵树，帮 Bob 计算出他最少要放置的士兵数。
Sol
状态：
f[i][0]表示i不放士兵时,以i为根的子树所需要的最小士兵数
f[i][1]表示i放士兵时,以i为根的子树所需要的最小士兵数
转移：
f[i][0]:i不放,那么它的子结点都要放
f[i][1]:i放,那么它的子结点可放可不放,取小即可
感觉比较板子题QwQ
Code
(It was written long long ago.)
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int r()
{
int x=,y=;;char ch;
ch=getchar();
while(ch<''||ch>'') {if(ch=='-') y=-;ch=getchar();}
while(ch>=''&&ch<='') {x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*y;
}
int n;
int num[];
bool ff[];
vector<int> son[];
int root;
void read()
{
n=r();
for(int i=;i<n;i++)
{
i=r();
num[i]=r();
for(int j=;j<=num[i];j++)
{
int x=r();
son[i].push_back(x);
ff[x]=;
}
}
while(ff[root]) root++;
}
int f[][];
void dp(int x)
{
f[x][]=;
f[x][]=;
if(num[x]==) return ;
for(int i=;i<num[x];i++)
{
int y=son[x][i];dp(y);
f[x][]+=f[y][];
f[x][]+=min(f[y][],f[y][]);
}
}
int main()
{
read();
dp(root);
int ans=min(f[root][],f[root][]);
printf("%d",ans);
return ;
}
随机推荐
-
行为驱动开发（BDD）实践示例
引言 BDD是对TDD理念的扩展.BDD强调有利害关系的技术团体和非技术团队都要参与到软件开发过程中.可以把它看成一种强调团体间合作的敏捷方法.大多数采用某种敏捷方法的团队最终都会遵循BDD的许多原则 ...
-
Nodejs报错集
1.ReferenceError: userModule is not defined A:1>检查app.js文件中是否调用userModule所在的文件(const userModule=r ...
-
深入SpringBoot:自定义PropertySourceLoader
http://www.jianshu.com/p/5206f74a4406 ********************************* 前言 上一篇文章介绍了SpringBoot的Enable ...
-
springMVC的详细步骤配置
使用springMVC也可以代替struts2,当然只是代替业务分发的功能,struts2的一些其他功能它是没有的,不然要struts2有什么用. 下面我用springMVC代替struts2去整合h ...
-
careercup-排序和查找 11.2
11.2 编写一个方法,对字符串数组进行排序,将所有变位词1排在相邻的位置. 类似leetcode:Anagrams 解法: 变位词:由变换某个词或短语的字母顺序构成的新的词或短语.例如,“trian ...
-
[Oracle] Listener的动态注册
在有Oracle Listener的动态注册之前,采用的是静态注册,所谓静态注册是指Oracle实例在启动时,读取listener.ora里的配置,然后注册到Listener,它主要有两个缺点: 1. ...
-
installation - How to install Synaptic Package Manager? - Ask Ubuntu
installation - How to install Synaptic Package Manager? - Ask Ubuntu How to install Synaptic Package ...
-
android在Canvas使用drawBitmap画一幅画
1.画图的主要方法 //Bitmap:图片对象,left:向左偏移.top: 顶部偏移 drawBitmap(Bitmap bitmap, float left, float top, Pai ...
-
字典（Tire树）
4189 字典 时间限制: 1 s 空间限制: 256000 KB 题目等级 : 大师 Master 题目描述 Description 最经,skyzhong得到了一本好厉害的字典,这个 ...
-
";malloc: * error for object 0x17415d0c0: Invalid pointer dequeued from free list * set a breakpoint in malloc_error_break to debug";;
I've fixed this error with Xcode 8 on iOS 8.3. I've just changed Deployment Target from 8.3 to 8.0. ...