Z_L_G

题解

总结(9) 训练赛(6)

/ 注册

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

算法入门-树上子链

题意一颗有n个结点的树，每个结点具有权值，求解最长（权值最大）的一条子链思路对于某一个结点来思考，他能构成的最长子链无非下列集中情况之一包含他的最长链+最长的包含他一个儿子的最长链所有结点均为负值，最长子链自身的权值他自己的一条最长链（另一条全负）因此我们维护一个dp数组，...

树形dp dp 深度优先搜索

2025-05-19

0 23

算法入门-二叉苹果树(边权转点权)

题意对于一个有n个结点的二叉树，根的编号一定为1，每条边有权值求保留q条边时，最多能获得多少权值 tip:分析样例可以知道，这棵树的根是必须保留的，“剪枝行为”一定是保留根含有根的子树思路由于输入是无规律的输入每一条边，所以应当先建立起二叉树，从根开始深搜建树由于边权是较难处理的，我...

dp 树形dp 深度优先搜索

2025-05-16

0 23

算法入门-(USACO 2008 Jan G)Cell Phone Network(最小支配集)

最小支配集选择一个点，可以覆盖相邻的点，覆盖所有点所需最小选点题意给定一颗n个结点的树，求最小支配集思路考虑每一个点，他可能被支配的方式有：被父亲支配，选自己，被儿子支配，维护一个二维dp数组记录点和状态：自己：父亲：儿子：对于自己和父亲，状态方程很显然可以推出，对于...

dp 树形dp 深度优先搜索最小支配集

2025-05-16

0 19

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

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

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

2025-05-15

0 19

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

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

dp 树形dp 深度优先搜索

2025-05-14

0 18

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

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

dp 树形dp 深度优先搜索

2025-05-14

0 21

算法入门-宝藏猎人

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

dp 深度优先搜索

2025-05-10

0 22

算法入门-[NOIP2005]过河

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

dp 路径压缩

2025-05-10

0 20

算法入门-拦截导弹

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

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

2025-05-06

0 23

算法入门-简单瞎搞题(分组背包+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 23