当前位置: 首页 > news >正文

详解洛谷P2016 战略游戏/BZOJ0495. 树的最小点覆盖之战略游戏(贪心/树形DP)

Description

Bob喜欢玩电脑游戏,特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。

他要建立一个古城堡,城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵,使得这些士兵能了望到所有的路。

注意,某个士兵在一个结点上时,与该结点相连的所有边将都可以被了望到。

请你编一程序,给定一树,帮Bob计算出他需要放置最少的士兵.

Format

Input

第一行 N,表示树中结点的数目。

第二行至第N+1行,每行描述每个结点信息,依次为:该结点标号i,k(后面有k条边与结点I相连)。

接下来k个数,分别是每条边的另一个结点标号r1,r2,…,rk。

对于一个n(0<n<=1500)个结点的树,结点标号在0到n-1之间,在输入数据中每条边只出现一次。

Output

输出文件仅包含一个数,为所求的最少的士兵数目。

Samples

输入数据 1

4
0 1 1
1 2 2 3
2 0
3 0

Copy

输出数据 1

1

Copy

Hint 答案为1(只要一个士兵在结点1上)。


思路1:树形DP

可以先看看详解洛谷P1352 没有上司的舞会(树形DP经典例题)-CSDN博客

定义状态dp[x][0/1]表示x这个节点不放/放士兵

根据题意,如果当前节点不放置士兵,那么它的子节点必须全部放置士兵,因为要满足士兵可以看到所有的边

dp[x][0] += dp[son][1]

其中son是u的子节点

如果当前节点放置士兵,只要将dp[x][1]加上它的子节点选不选的最小值就行了(因为树形dp自下而上,上面的节点不需要考虑)

dp[x][1]+=min(dp[son][0],dp[son][1])


代码(树形DP)

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,u,v,dp[10001][2];
vector<int> vec[100001];
void dfs(int fa,int x)
{dp[x][1] = 1;for(int i = 0;i < vec[x].size();i++)if(vec[x][i] != fa){dfs(x,vec[x][i]);dp[x][0] += dp[vec[x][i]][1];dp[x][1] += min(dp[vec[x][i]][0],dp[vec[x][i]][1]);}
}
signed main()
{cin>>n;for(int i = 1;i <= n;i++){int p;cin>>p>>u;for(int j = 1;j <= u;j++){cin>>v;vec[p].push_back(v);vec[v].push_back(p);}}dfs(-1,0);cout<<min(dp[0][1],dp[0][0]);return 0;
}

思路2:贪心

可以按照反方向的深度优先遍历序列来进行贪心。每检查一个结点,如果当前点和当前点的父节点都不属于顶点覆盖集合,则将父节点加入到顶点覆盖集合,并标记当前节点和其父节点都被覆盖.

虽然说着思路很简单,但是代码细节蛮多的,可以参考一下。


 代码(贪心)

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,u,v,ans,fat[100001],cnt;
struct st
{int zhi,id;
}dp[100001];
bool vis[100001];
vector<int> vec[100001];
void dfs(int fa,int x,int dep)
{dp[++cnt] = {dep,x};fat[x] = fa;for(int i = 0;i < vec[x].size();i++)if(vec[x][i] != fa)dfs(x,vec[x][i],dep + 1);
}
bool cmp(st x,st y)
{return x.zhi > y.zhi;
}
signed main()
{cin>>n;for(int i = 1;i <= n;i++){int p;cin>>p>>u;for(int j = 1;j <= u;j++){cin>>v;vec[p].push_back(v);vec[v].push_back(p);}}vis[1501] = 1;dfs(1501,0,1);sort(dp + 1,1 + dp + n,cmp);for(int i = 1;i <= n;i++)if(vis[dp[i].id] == 0 && vis[fat[dp[i].id]] == 0){vis[fat[dp[i].id]] = 1;vis[dp[i].id] = 1;ans++;}cout<<ans;return 0;
}

结语 

 如果这篇博客对您有帮助的话,请点赞收藏关注支持一下呗!(o゜▽゜)o☆

相关文章:

详解洛谷P2016 战略游戏/BZOJ0495. 树的最小点覆盖之战略游戏(贪心/树形DP)

Description Bob喜欢玩电脑游戏&#xff0c;特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。 他要建立一个古城堡&#xff0c;城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵&#xff0c;使得这些士兵能了望到所有的路。 注意&…...

解决The Tomcat connector configured to listen on port 8080 failed to start

问题 启动javar报错&#xff0c;提示如下 Description: The Tomcat connector configured to listen on port 8080 failed to start. The port may already be in use or the connector may be misconfigured. Action: Verify the connector’s configuration, identify a…...

深度学习自然语言处理(NLP)模型BERT:从理论到Pytorch实战

文章目录 深度学习自然语言处理&#xff08;NLP&#xff09;模型BERT&#xff1a;从理论到Pytorch实战一、引言传统NLP技术概览规则和模式匹配基于统计的方法词嵌入和分布式表示循环神经网络&#xff08;RNN&#xff09;与长短时记忆网络&#xff08;LSTM&#xff09;Transform…...

C语言的循环结构

目录 前言 1.三种循环语句 1.while循环 2.for循环 2.1缺少表达式的情况 3.do while循环 2.break语句和continue语句 2.1在while循环中 2.2在for循环中 2.3在do while 循环中 3.循环的嵌套 4.go to语句 前言 C语⾔是结构化的程序设计语⾔&#xff0c;这⾥的结构指的是…...

C#用Array类的FindAll方法和List<T>类的Add方法按关键词在数组中检索元素并输出

目录 一、使用的方法 1. Array.FindAll(T[], Predicate) 方法 &#xff08;1&#xff09;定义 &#xff08;2&#xff09;示例 2.List类的常用方法 &#xff08;1&#xff09;List.Add(T) 方法 &#xff08;2&#xff09;List.RemoveAt(Int32) 方法 &#xff08;3&…...

【前后端接口AES+RSA混合加解密详解(vue+SpringBoot)附完整源码】

前后端接口AES+RSA混合加解密详解(vue+SpringBoot) 前后端接口AES+RSA混合加解密一、AES加密原理和为什么不使用AES加密二、RSA加密原理和为什么不使用rsa加密三、AES和RSA混合加密的原理四、代码样例前端1. 请求增加加密标识2. 前端加密工具类3.前端axios请求统一封装,和返…...

React环境配置

1.安装Node.js Node.js官网&#xff1a;https://nodejs.org/en/ 下载之后按默认选项安装好 重启电脑即可自动完成配置 2.安装React 国内使用 npm 速度很慢&#xff0c;可以使用淘宝定制的 cnpm (gzip 压缩支持) 命令行工具代替默认的 npm。 ①使用 winR 输入 cmd 打开终端 ②依…...

Pandas 数据处理-排序与排名的深度探索【第69篇—python:文本数据处理】

文章目录 Pandas 数据处理-排序与排名的深度探索1. sort_index方法2. sort_values方法3. rank方法4. 多列排序5. 排名方法的参数详解6. 处理重复值7. 对索引进行排名8. 多级索引排序与排名9. 更高级的排序自定义10. 性能优化技巧10.1 使用nsmallest和nlargest10.2 使用sort_val…...

第8节、双电机多段直线运动【51单片机+L298N步进电机系列教程】

↑↑↑点击上方【目录】&#xff0c;查看本系列全部文章 摘要&#xff1a;前面章节主要介绍了bresenham直线插值运动&#xff0c;本节内容介绍让两个电机完成连续的直线运动,目标是画一个正五角星 一、五角星图介绍 五角星总共10条直线&#xff0c;10个顶点。设定左下角为原点…...

Elasticsearch:基本 CRUD 操作 - Python

在我之前的文章 “Elasticsearch&#xff1a;关于在 Python 中使用 Elasticsearch 你需要知道的一切 - 8.x”&#xff0c;我详细讲述了如何建立 Elasticsearch 的客户端连接。我们也详述了如何对数据的写入及一些基本操作。在今天的文章中&#xff0c;我们针对数据的 CRUD (cre…...

1992-2022年全国及31省对外开放度测算数据(含原始数据+计算结果)(无缺失)

1992-2022年全国及31省对外开放度测算数据&#xff08;含原始数据计算结果&#xff09;&#xff08;无缺失&#xff09; 1、时间&#xff1a;1992-2022年 2、来源&#xff1a;各省年鉴、国家统计局、统计公报、 3、指标&#xff1a;进出口总额&#xff08;万美元&#xff09…...

JVM之GC垃圾回收

GC垃圾回收 如何判断对象可以回收 引用计数法 如果有对象引用计数加一&#xff0c;没有对象引用&#xff0c;计数减一&#xff0c;如果计数为零&#xff0c;则回收 但是如果存在循环引用&#xff0c;即A对象引用B对象&#xff0c;B对象引用A对象&#xff0c;会造成内存泄漏 可…...

自然语言学习nlp 六

https://www.bilibili.com/video/BV1UG411p7zv?p118 Delta Tuning&#xff0c;尤其是在自然语言处理&#xff08;NLP&#xff09;和机器学习领域中&#xff0c;通常指的是对预训练模型进行微调的一种策略。这种策略不是直接更新整个预训练模型的权重&#xff0c;而是仅针对模型…...

fpga 需要掌握哪些基础知识?

个人根据自己的一些心得总结一下fpga 需要掌握的基础知识&#xff0c;希望对你有帮助。 1、数电&#xff08;必须掌握的基础&#xff09;&#xff0c;然后进阶学模电&#xff0c; 2、掌握HDL&#xff08;verilog或VHDL&#xff09;一般建议先学verilog&#xff0c;然后可以学…...

Qt未来市场洞察

跨平台开发&#xff1a;Qt作为一种跨平台的开发框架&#xff0c;具有良好的适应性和灵活性&#xff0c;未来将继续受到广泛应用。随着多设备和多平台应用的增加&#xff0c;Qt的前景在跨平台开发领域将更加广阔。 物联网应用&#xff1a;由于Qt对嵌入式系统和物联网应用的良好支…...

GPT-4模型中的token和Tokenization概念介绍

Token从字面意思上看是游戏代币&#xff0c;用在深度学习中的自然语言处理领域中时&#xff0c;代表着输入文字序列的“代币化”。那么海量语料中的文字序列&#xff0c;就可以转化为海量的代币&#xff0c;用来训练我们的模型。这样我们就能够理解“用于GPT-4训练的token数量大…...

宽字节注入漏洞原理以及修复方法

漏洞名称:宽字节注入 漏洞描述: 宽字节注入是相对于单字节注入而言的&#xff0c;该注入跟HTML页面编码无关&#xff0c;宽字节注入常见于mysql中&#xff0c;GB2312、GBK、GB18030、BIG5、Shift_JIS等这些都是常说的宽字节&#xff0c;实际上只有两字节。宽字节带来的安全问…...

【Linux】SystemV IPC

进程间通信 一、SystemV 共享内存1. 共享内存原理2. 系统调用接口&#xff08;1&#xff09;创建共享内存&#xff08;2&#xff09;形成 key&#xff08;3&#xff09;测试接口&#xff08;4&#xff09;关联进程&#xff08;5&#xff09;取消关联&#xff08;6&#xff09;释…...

iview 页面中判断溢出才使用Tooltip组件

使用方法 <TextTooltip :content"contentValue"></TextTooltip> 给Tooltip再包装一下 <template><Tooltip transfer :content"content" :theme"theme" :disabled"!showTooltip" :max-width"300" :p…...

如何使用websocket

如何使用websocket 之前看到过一个面试题&#xff1a;吃饭点餐的小程序里&#xff0c;同一桌的用户点餐菜单如何做到的实时同步&#xff1f; 答案就是&#xff1a;使用websocket使数据变动时服务端实时推送消息给其他用户。 最近在我们自己的项目中我也遇到了类似问题&#xf…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...