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 ;
}
随机推荐
-
夺命雷公狗---node.js---17之项目的构建在node+express+mongo的博客项目2之一，二级路由
然后我们就来开始搭建后台了... 不过后台我们可以来玩玩他的二级路由... 然后再去修改下他们的样式即可......修改方法和刚才那里的修改方法一样, 访问效果如下所示: OK,已经正常相识了
-
寻找Harris、Shi-Tomasi和亚像素角点
Harris.Shi-Tomasi和亚像素角点都是角点,隶属于特征点这个大类(特征点可以分为边缘.角点.斑点). 一.Harris角点检测是一种直接基于灰度图像的角点提取算法,稳定性较高,但是也可能出 ...
-
关于tensorboard启动问题
我在学习过程中遇到了tensorboard无法启动的问题. 按照网上的教程,我无法正常启动tensorboard,全过程没有报错,但是打开tensorboard显示 No dashboards are ...
-
有用的SAP System Administration T-CODE
一,SAP系统管理常用到的事务代码1. SM51 SAP Servers System Monitoring2. SM21 SAP系统日志3. SRZL SAP计算机中心管理系统(CCMS) ...
-
【Android】接入有米广告SDK
测试:接入有米广告SDK(测试广告). 步骤: 1.注册并登录有米广告. 2.下载相应的SDK,这里我选了第一个[Android广告SDK ],如下图: 3.下好后,根据doc文档步骤进行操作,包括: ...
-
C++对象的内存布局以及虚函数表和虚基表
C++对象的内存布局以及虚函数表和虚基表 本文为整理文章, 参考: http://blog.csdn.net/haoel/article/details/3081328 http://blog.csd ...
-
《转》python学习--基础上
学习的python本来想自己总结,但是发现了一篇不错的大牛的博客,拿来主义,,又被我实践了 关于前两篇如果总结的不详细,因此把他人的转载过来 http://www.cnblogs.com/BeginM ...
-
MongoDB 排序文档
sort() 方法 要在 MongoDB 中的文档进行排序,需要使用sort()方法. sort() 方法接受一个文档,其中包含的字段列表连同他们的排序顺序. 要指定排序顺序1和-1. 1用于升序排列 ...
-
var_dump — 打印变量的相关信息
<?php $a = array( 1 , 2 , array( "a" , "b" , "c" )); var_dump ( $a ...
-
BZOJ 1009 GT考试 (AC自动机 + 矩阵乘法加速dp)
题目链接: https://www.lydsy.com/JudgeOnline/problem.php?id=1009 题意: 准考证号为\(n\)位数\(X_1X_2....X_n(0<=X_ ...