Z_L_G

题解

总结(19) 训练赛(13)

/ 注册

全部文章 / 题解（共105篇）

算法入门-Strategic game(最小点覆盖)

最小点覆盖选择一个点，覆盖所有相邻边，最少选几个点能覆盖所有边题意给定一棵n个结点的树，选定一个结点后即可覆盖他的所有邻边，求覆盖所有邻边的最少选定结点数思路动态规划对于每一个结点，由于覆盖边，所以自己考虑选和不选两种情况，且父亲没选，自己就一定得选，父亲选了，自己就可选可不选...

dp 树形dp 深度优先搜索最小点覆盖

2025-05-15

0 34

算法入门-小G有一个大树

题意对于一棵树，我们希望找到一个点，使得删除这个点之后，最大子树的结点数最小以边的形式输入，输出被删除的点的编号和删除后最大子树的结点数思路考虑用无根树描述，对于树的某一个结点，删掉后，整棵树变为两部分这个结点的父亲所属的树这个结点的若干子树故另表示删除这个点后最大子树结点...

dp 树形dp 深度优先搜索

2025-05-14

0 43

算法入门-没有上司的舞会

题意给定一颗n个结点的树，结点编号1~n，每个结点有权值，一个点选择以后，它的父亲就不可以被选，输出能选出的最大权值思路对于每个点，都有选和不选两种情况，当一个点选的时候，所有的儿子都不能选，当一个点不选的时候，每个儿子取选和不选的最大值即可，维护一个二维dp数组，状态转移方程如下注...

dp 树形dp 深度优先搜索

2025-05-14

0 49

算法入门-宝藏猎人

题意共有0~30000编号的岛，有n个宝藏，你每次只能往编号大的方向走，走的步长只能是上一次走的步长+p（p=-1,0,1），第一步走了d，求最多能拿到多少宝藏思路本题应该使用dfs+剪枝是更好写的 dp 对于0~30000这个范围，从1开始走，最大的偏移量不超过300 即相较于第一步...

dp 深度优先搜索

2025-05-10

0 41

算法入门-[NOIP2005]过河

题意给定桥的长度L，每一步可以走S~T中任意距离，桥上共有M颗石子，求走过桥最少踩多少石子 0<= L <=1e9, 1<=S<=T<=10, 1<=M<=100 思路一个类似于走楼梯的动态规划，很显然的可以得到转移方程:其中，S<=j<...

dp 路径压缩

2025-05-10

0 46

算法入门-拦截导弹

题意有若干导弹，拦截系统只能拦高度降序的一组导弹，问一套系统最多拦截多少导弹，拦截全部导弹需要几套系统思路对于第一个问题，直接对整个序列跑一个最长递减子序列(LDS Longest-Decreasing-Subsequence) 对于第二个问题，正解是跑一个最长递增子序列(LIS)...

dp 最长递增子序列最长递减子序列

2025-05-06

0 47

算法入门-简单瞎搞题(分组背包+bitset优化)

题意有n个区间，从每个区间中取一个值求的种数思路分组背包，考虑前i组能不能凑出j，，其中k属于a[i] 双层枚举i,j,对于每一个j枚举区间，O(100*1000000*100)=O(1e10),过不了一点 for(int i=1;i<=n;i++){ fo...

dp 分组背包 bitset

2025-05-06

0 53

算法入门-[NOIP2004]合唱队形

题意共有n个人，每个人有身高，移除若干人，使得序列为{纯升序||纯降序||先升序后降序}，求最少的移除人数思路方法1：对于整个序列正着求一个最长上升子序列，反着求一个最长上升子序列，枚举每个位置两个序列和，最大的减一即为序列最长长度。方法2：维护一个二维dp数组，第二维记录当前元素属于...

dp 最长上升子序列

2025-05-06

0 39

算法入门-石子合并

题意给定n堆石子，成环放置，每堆石子有自己的重量，每次合并可以合并相邻的两堆，合并的得分是两堆石子重量和，求解把所有石子合并成一堆所得的最大得分和最小得分思路由于两堆石子是相邻的，所以每一次合成其实是对一个区间中的两堆的分界做考虑，下面按求最大得分考虑，如一共1~5，合并1~5的最后一次...

dp 区间dp

2025-05-04

0 56

算法入门-田忌赛马

题意齐王和田忌各有n匹马，田忌赢得200，输得-200，平局不得钱，请你安排顺序，解出可获得的最大钱数思路先将齐王和田忌的马降序排序贪心：对于齐王的第k匹马，田忌如果能赢就直接选当前第一匹马，如果不能赢就选择最后一匹马对于平局的情况，选择第一匹和最后一匹都有可能导致错误决策...

dp 区间dp

2025-05-03

0 66