GESP202512六级解析
第一道题 路径覆盖
1. 题目简述
题目核心：给定一棵有根树，根节点为 1。我们需要选择若干个节点染成黑色，每个节点 \(i\) 都有一个染色代价 \(c_i\)。 目标：使得所有从叶子节点到根节点的路径上，都至少包含一个黑色节点，并使得总代价最小。
2. 解题思路：树形动态规划 (Tree DP)
这就一道非常经典的树形 DP 题目。对于树上的任意一个节点 \(u\)，要阻断经过它的所有路径，我们只有两种决策：
决策一：在当前节点 \(u\) 染色
如果我们选择花费 \(c_u\) 将节点 \(u\) 染黑，那么无论 \(u\) 的子树情况如何，经过 \(u\) 的路径都在这里被截断了。 代价：\(c_u\)
决策二：不在当前节点 \(u\) 染色
如果我们不染黑 \(u\)，为了保证条件成立（路径必须被截断），我们必须指望 \(u\) 的所有子节点（儿子们）各自解决好它们自己子树的路径阻断问题。 代价：所有子节点最小代价之和，即 \(\sum dp[v]\) （其中 \(v\) 是 \(u\) 的子节点）。
状态转移方程
定义 \(dp[u]\) 为：覆盖以 \(u\) 为根的子树所需的最小代价。
边界条件（叶子节点）： 如果 \(u\) 是叶子节点，它没有子节点。如果不染黑它，路径就会直通根部（在以它为根的子树视角下无法阻断）。因此，叶子节点的 \(dp[u]\) 只能取它自身的代价。 $$ dp[u] = c_u \quad (\text{当 } u \text{ 为叶子时}) $$
3. 关键点与坑点
-
数据范围陷阱： 题目中 \(N \le 10^5\)，且单点代价 \(c_i \le 10^9\)。 如果是链状结构，代价累加可能会超过
int的最大范围（约 \(2 \times 10^9\)）。因此，必须使用long long来存储 DP 数组和累加和，否则大概率只能拿部分分数。 -
建图方式：
- 第二行输入是从2号结点开始的
- 输入给的是每个节点的“父亲”，但 DFS 需要从父找子。因此需要使用邻接表（
vector<int> adj[N]）来存储树结构。
4. AC 代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> abj[N]; // 邻接表
int c[N];
long long dfs(int curr){
if (abj[curr].empty()){
return c[curr];
}
long long currCost = c[curr]; // 当前结点的代价
long long sunsCost = 0; // 计算所有儿子结点的代价
for (int p: abj[curr]){
sunsCost += dfs(p);
}
return min(currCost, sunsCost);
}
int main() {
int n;
cin >> n;
for (int i=2; i<=n; i++){
int t; cin >> t;
abj[t].push_back(i);
}
for (int i=1; i<=n; i++){
cin >> c[i];
}
cout << dfs(1);
}
5. 总结
这道题考察了对树形结构的理解以及简单的动态规划思想。
- 难点：在于正确推导出“当前节点代价”与“子节点代价之和”的博弈关系。
- 易错点：在于 long long 的使用。
第二题 道具商店
1. 题目简述
场景：商店里有 \(n\) 件道具，每件道具提供 \(a_i\) 点攻击力，售价 \(c_i\) 金币。每件道具只能买一次。
限制：你手头有 \(k\) 枚金币。
目标：在不超过金币上限 \(k\) 的前提下，购买道具使得总攻击力最大。
2. 陷阱分析：为什么传统 0/1 背包会死机？
乍一看，这道题就是最标准的 0/1 背包问题：
- 物品 = 道具
- 体积（限制）= 金币价格 \(c_i\)
- 价值（目标）= 攻击力 \(a_i\)
按照传统套路，我们通常定义状态 \(dp[j]\) 为：花费 \(j\) 金币能获得的最大攻击力。 转移方程：\(dp[j] = \max(dp[j], dp[j - c_i] + a_i)\)
但是，请看数据范围: 金币上限 \(k \le 10^9\)（10 亿）。
如果我们开一个 int dp[1000000005] 的数组，内存需要约 4GB，这远远超过了竞赛题目通常允许的 128MB 或 256MB 限制。直接这样写会报 MLE (Memory Limit Exceeded)。
3. 解题思路：价值与体积的“反向互换”
既然金币（体积）太大不能做数组下标，那我们看看攻击力（价值）？
- 物品数量 \(n \le 500\)
- 单件最大攻击力 \(a_i \le 500\)
- 最大可能的总攻击力 \(= 500 \times 500 = 250,000\)
这个数字非常小！完全可以作为数组的下标。因此，我们采用 “状态定义互换” 的技巧：
新的状态定义
定义 \(dp[j]\) 为：获得正好 \(j\) 点攻击力，最少需要花费多少金币。
状态转移方程
对于第 \(i\) 个物品（攻击力 \(a_i\)，花费 \(c_i\)）： $$ dp[j] = \min(dp[j], dp[j - a_i] + c_i) $$
初始化与答案
- 初始化：
- \(dp[0] = 0\) （获得 0 攻击力不需要花钱）。
- 其他 \(dp[j]\) 初始化为无穷大（
1e17），表示尚未达成该攻击力。
- 寻找答案：
- DP 跑完后，从最大可能的总攻击力（250,000）开始倒序遍历。
- 找到第一个满足 \(dp[j] \le k\) 的 \(j\)，这个 \(j\) 就是我们能买到的最大攻击力。
4. 关键细节
- 数组大小：一定要开到 \(250,000\) 以上，而不是 \(n\) 的大小。建议开到 \(250500\) 防止越界。
- 数据类型：虽然攻击力是
int，但在 DP 过程中累加的金币花费可能会超过int（虽然题目说 \(c_i\) 单个很大，但 \(k\) 也是 \(10^9\)，不过为了保险起见以及处理无穷大初始值，DP 数组建议用long long）。
5. AC 代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 250000 + 10;
int n, k;
int a[550], c[550]; // 攻击力/金币数量
long long dp[N]; // 前i个物品凑齐攻击力为j的最少金币数量
int main() {
cin >> n >> k;
for (int i=1; i<=N; i++) dp[i] = 1e17 + 10;
for (int i=1; i<=n; i++) cin >> a[i] >> c[i];
for (int i=1; i<=n; i++){
for (int j=N-5; j>=a[i]; j--){
dp[j] = min(dp[j], dp[j-a[i]] + c[i]);
}
}
for (int i=N; i>=0; i--){
if (dp[i] <= k){
cout << i;
break;
}
}
}