hackerchef - 博客园

2025年7月

洛谷题单指南-树与图上的动态规划-P7077 [CSP-S2020] 函数调用

摘要：原题链接：https://www.luogu.com.cn/problem/P7077 题意解读：一个整数序列，有三种函数：1、做单点加法 2、做所有数乘法 3、调用其他函数，给出Q个函数调用按顺序执行，输出整数序列的结果。解题思路： 1、朴素想法直接做，对序列的修改借助于线段树，总体复杂度在O 阅读全文

posted @ 2025-07-06 00:10 hackerchef 阅读(36) 评论(0) 推荐(0)

洛谷题单指南-树与图上的动态规划-P3953 [NOIP 2017 提高组] 逛公园

摘要：原题链接：https://www.luogu.com.cn/problem/P3953 题意解读：设dist[n]表示1到n的最短路径，求1~n的所有路径中长度不超过dist[n] + k的条数。解题思路：由于k的范围0~50，可以考虑枚举所有路径长度的数量：dist[n]、dist[n]+1、阅读全文

posted @ 2025-07-02 14:41 hackerchef 阅读(57) 评论(0) 推荐(0)

2025年6月

洛谷题单指南-树与图上的动态规划-P2986 [USACO10MAR] Great Cow Gathering G

摘要：原题链接：https://www.luogu.com.cn/problem/P2986 题意解读：一棵树中，边权是距离，点权是人数，找到一个点到所有人距离之和最小，求这个最小距离和。解题思路：换根DP的典型题，思路可以参考：https://chuna2.787528.xyz/hackerchef/p 阅读全文

posted @ 2025-06-30 15:51 hackerchef 阅读(71) 评论(0) 推荐(0)

洛谷题单指南-树与图上的动态规划-P2515 [HAOI2010] 软件安装

摘要：原题链接：https://www.luogu.com.cn/problem/P2515 题意解读：在一个非联通图中，每个点有体积有价值，求选取不超过m体积的节点的最大价值，选择一个点必须选择其父节点。解题思路：由于是非联通图，又由于有可能存在环，而环中任选一个点其他所有点都要选。因此，可以先用阅读全文

posted @ 2025-06-30 14:16 hackerchef 阅读(31) 评论(0) 推荐(0)

洛谷题单指南-树与图上的动态规划-P1273 有线电视网

摘要：原题链接：https://www.luogu.com.cn/problem/P1273 题意解读：给定一棵树，边权是成本，叶子节点的点权是收益，求总收益不为负的情况，从根节点能覆盖的最多叶子数量。解题思路：有依赖的背包问题。 1、状态表示设f[i][j]表示以i为根的子树中选择的叶子节点数是j 阅读全文

posted @ 2025-06-27 09:45 hackerchef 阅读(28) 评论(0) 推荐(0)

洛谷题单指南-树与图上的动态规划-P2585 [ZJOI2006] 三色二叉树

摘要：原题链接：https://www.luogu.com.cn/problem/P2585 题意解读：给二叉树节点染色（红、绿、蓝），父子节点不能同色，兄弟节点不能同色，问最多可以有多少绿色，最少可以有多少绿色。解题思路：首先，要根据给定的二叉树序列建树，可以看出二叉树序列是按照DFS顺序给出，序列阅读全文

posted @ 2025-06-26 10:33 hackerchef 阅读(46) 评论(0) 推荐(0)

洛谷题单指南-树与图上的动态规划-P2016 战略游戏

摘要：原题链接：https://www.luogu.com.cn/problem/P2016 题意解读：在树中选择最少的节点，使得可以覆盖整个树，一个节点可以覆盖所有分支以及子节点。解题思路： 1、状态表示 f[i][0]表示以i为根的子树且不选i的最少士兵数量，f[i][1]表示以i为根的子树且选i的阅读全文

posted @ 2025-06-25 15:24 hackerchef 阅读(28) 评论(0) 推荐(0)

洛谷题单指南-树与图上的动态规划-P1122 最大子树和

摘要：原题链接：https://www.luogu.com.cn/problem/P1122 题意解读：在一颗树中，求一片连通区域最大的点权和（美味指数）。解题思路：树中的一片连通区域必然是以某个根节点为子树的一部分。设f[i][0]表示以i为根的子树且不选i的最大美味指数，f[i][1]表示以i为阅读全文

posted @ 2025-06-25 11:10 hackerchef 阅读(51) 评论(0) 推荐(0)

洛谷题单指南-树与图上的动态规划-P1040 [NOIP 2003 提高组] 加分二叉树

摘要：原题链接：https://www.luogu.com.cn/problem/P1040 题意解读：计算最高加分，以及前序遍历。解题思路：用递归+记忆化搜索比较直观，关键点是如何记录方案设f[i][j]表示从i到j的最大加分值，用于记忆化搜索，设g[i][j]记录最大加分值的分割点，也就是树的根阅读全文

posted @ 2025-06-24 16:49 hackerchef 阅读(28) 评论(0) 推荐(0)

洛谷题单指南-树与图上的动态规划-P2656 采蘑菇

摘要：原题链接：https://www.luogu.com.cn/problem/P2656 题意解读：有向图中，有边权，重复走获得边权值乘上系数，系数只有一位小数，问从起点能走过的路径的最大边权和。解题思路：既然可以重复走，可以先求强联通分量，对强联通分量进行缩点，并计算缩点内所有路径反复走能得到的阅读全文

posted @ 2025-06-24 10:33 hackerchef 阅读(29) 评论(0) 推荐(0)

公告