首页 > 其他分享 >luoguP2016 战略游戏

luoguP2016 战略游戏

时间:2024-11-03 15:31:12浏览次数:1  
标签:std luoguP2016 游戏 int self dfs 战略 adj dp

给定一棵n个结点的树,至少要选多少个点才能覆盖所有边?边的两个端点至少有一个被选中则认为覆盖。
1<=n<=1500

分析:设dp[i][0]表示以i为根的子树,不选i的答案,同理dp[i][1]为选i的答案。自下而上dp,如果选了i,那么其子节点可以选或不选;如果不选i,那么其子节点必须选。

#include <bits/stdc++.h>
using i64 = long long;

void solve() {
	int n;
	std::cin >> n;
	std::vector<std::vector<int>> adj(n);
	for (int i = 0; i < n; i++) {
		int x, y;
		std::cin >> x >> y;
		for (int j = 0; j < y; j++) {
			int z;
			std::cin >> z;
			adj[x].push_back(z);
			adj[z].push_back(x);
		}
	}

	std::vector<std::array<int,2>> dp(n);

	auto dfs = [&](auto self, int x, int p) -> void {
		dp[x][0] = 0;
		dp[x][1] = 1;
		for (auto i : adj[x]) if (i != p) {
			self(self, i, x);
			dp[x][0] += dp[i][1];
			dp[x][1] += std::min(dp[i][0], dp[i][1]);
		}
	};

	dfs(dfs, 0, 0);

	std::cout << std::min(dp[0][0], dp[0][1]) << "\n";
}

int main() {
	std::cin.tie(0)->sync_with_stdio(0);
	int t = 1;
	while (t--) solve();
	return 0;
}

标签:std,luoguP2016,游戏,int,self,dfs,战略,adj,dp
From: https://www.cnblogs.com/chenfy27/p/18523491

相关文章

  • luoguP1005 矩阵取数游戏
    有n*m的矩阵,每个元素a[i][j]均为非负整数,游戏规则如下:每轮从每行各取一个元素,共n个。经过m轮后取完所有元素。每次取走的元素只能是该元素所在行的行首或行尾。每轮取数都有一个分值,为每行取数的得分之和,每行取数的得分为被取走的元素值乘以2的i次方,其中i为取数轮次,从1开始。......
  • 《漫威复仇者联盟》游戏辅助工具修改器风灵月影版操作教程详解
    《漫威复仇者联盟》是一款基于漫威超级英雄的第三人称动作冒险游戏,玩家可以操控各种超级英雄完成任务和挑战。风灵月影版的修改器为这款游戏提供了多种便捷功能,帮助玩家更轻松地探索游戏世界,提升游戏体验。以下是《漫威复仇者联盟》游戏辅助工具修改器风灵月影版的操作教程详解......
  • C++ 实现俄罗斯方块游戏
    ✅作者简介:2022年博客新星第八。热爱国学的Java后端开发者,修心和技术同步精进。......
  • 【河北建筑工程学院毕业论文】基于Spring Boot架构的游戏商城的设计与实现
    注:仅展示部分文档内容和系统截图,需要完整的视频、代码、文章和安装调试环境请私信up主。摘要随着互联网技术的发展,游戏行业遇到了前所未有的发展和机遇。游戏商城是游戏行业中的一个重要组成部分,为游戏玩家提供了游戏购买、下载、充值等全方位服务。随着游戏用户的快速增......
  • 找数游戏 [循环]
    描述一个三位数,各位数字互不相同,十位数字比个位、百位数字之和还要大,且十位、百位数字之和不是质数。桐桐想把符合上述条件的三位数找出来,你能帮助她吗?输入描述无输出描述按照从小到大的顺序,输出满足条件的三位数,每行一个。#include<bits/stdc++.h>usingnamespacestd......
  • 贪吃蛇小游戏C++
    //禁用特定的编译器警告#pragmawarning(disable:4996)//包含所需的头文件#include<iostream>#include<windows.h>//用于系统调用,如清屏#include<time.h>//用于生成随机数和时间函数#include<conio.h>//用于键盘输入,如kbhit()和getch()//定义棋盘的尺寸#......
  • C++游戏代码
        这是我们班一个大聪明LQH做的,大家看看怎么样,如果很好,关注sum不想++,他能告诉你彩damn.#include<bits/stdc++.h>#include<windows.h>usingnamespacestd;voidmai(intxxx,intx1,intx2,intx3,intma11,intma12,intma13,intma21,intma22,intma23,in......
  • 学霸带你游戏化 Python 编程知识轻松上手
    Python基础与游戏开发包在游戏开发的世界里,Python以其简单易用的特性而备受推崇。无论是独立游戏还是大型项目,Python都能在开发过程中发挥重要作用。通过了解Python的基础知识,开发者不仅能提升编程能力,还能更好地应对游戏设计中的各种挑战。接下来,我们将深入探讨Python......
  • 学霸带你游戏化挑战自我的学习策略
    高效学习的策略与方法在信息爆炸的时代,如何高效学习成为了许多人的迫切需求。通过分阶段学习,可以帮助学习者更加系统地掌握知识,从明确学习目标到制定学习计划,再到实施阶段性学习,强化记忆与理解,最后评估与反馈,整个过程构成了一个完整的学习闭环。借助于具体的游戏和实际的工具,......
  • 动态规划 —— 路径问题-地下城游戏
    1. 地下城游戏题目链接:174.地下城游戏-力扣(LeetCode)https://leetcode.cn/problems/dungeon-game/description/ 2. 算法原理 状态表示:以莫一个位置位置为结尾或者以莫一个位置为起点  dp[i,j]表示:到达[i,j]位置的时候,骑士所需要的最低初始健康点数(X),这个状......