Z_L_G

分类

总结(9) 训练赛(6) 题解(68)

/ 注册

全部文章（共6篇）

算法入门-树上子链

题意一颗有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