E. 水母与五月花号 详细题解

问题重述

我们有一个 $n$ 个顶点、$m$ 条边的有向无环图（DAG），所有边 $u \to v$ 满足 $u < v$。

• 每个顶点 $i$ 有一个商人，可以无限次购买价格为 $c_i$、威力为 $w_i$ 的卡牌。
• 从顶点 $1$ 出发，带 $r$ 枚初始金币，沿着有向边走到目标顶点 $p$。
• 只能在当前所在顶点购买卡牌。
• 目标：最大化购买的卡牌威力总和。

需要回答 $q$ 个询问，每个询问给定目标顶点 $p$ 和初始金币 $r$。

关键观察

引理 1

考虑从 $1$ 到 $p$ 的任意一条路径 $s_1, s_2, \dots, s_k$。设 $z$ 是该路径上 $\frac{w_z}{c_z}$ 最大的顶点（即性价比最高的顶点），记 $C = c_z$，$W = w_z$。

引理： 存在一个最优解，其中从其他顶点购买的卡牌（称为特殊卡牌）数量不超过 $C$ 张。

证明思路：

• 设特殊卡牌的成本序列为 $c_1', c_2', \dots, c_k'$，前缀和为 $p_i' = \sum_{j=1}^i c_j'$。
• 根据鸽巢原理，$C+1$ 个前缀和模 $C$ 必有两个相等。
• 这两个相等前缀和之间的卡牌总成本是 $C$ 的倍数，可以用若干张 $z$ 点的卡牌替换。
• 由于 $z$ 的性价比最高，替换后答案不会变差。

推论： 特殊卡牌的总成本不超过 $\max(c)^2$。

核心思想

将问题分成两部分：

1. 小 $r$ 情况（$r \le \max(c)^2$）：直接 DP
2. 大 $r$ 情况（$r > \max(c)^2$）：利用引理，枚举最优性价比顶点

第一部分：小 $r$ 情况的 DP

定义：

$$f(u, x) = \text{当前在顶点 } u \text{，总花费为 } x \text{ 时的最大威力总和} $$

转移：

• 购买卡牌：$f(u, x + c_u) = \max(f(u, x + c_u), f(u, x) + w_u)$
• 沿着边移动：$f(v, x) = \max(f(v, x), f(u, x))$，其中 $u \to v$ 有边

初始化：$f(1, 0) = 0$，其余为 $-\infty$。

复杂度：$O(m \cdot \max(c)^2)$，由于 $n \le 200, \max(c) \le 200$，$\max(c)^2 \le 40000$，可行。

查询时直接输出 $f(p, r)$。

第二部分：大 $r$ 情况的 DP

当 $r > \max(c)^2$ 时，根据引理，我们可以：

1. 枚举每个顶点 $i$ 作为性价比最高的顶点
2. 假设在顶点 $i$ 购买 $t$ 张卡牌（$t$ 可能为负，表示用其他卡牌替换）

定义：

$$g(i, u, x, 0/1) = \text{当前在顶点 } u \text{，性价比最高顶点为 } i \text{，当前花费模 } c_i \text{ 余 } x \text{，是否已经到达过顶点 } i \text{ 时的最大威力} $$

关键技巧：当花费达到 $c_i$ 时，立即用一张 $i$ 点的卡牌替换，使得花费模 $c_i$ 始终小于 $c_i$。

具体实现：

• 记 $a = c_i$，$b = w_i$
• 对于顶点 $i$ 本身：当 $x = 0$ 时，$g(i, i, 0, 1) = 0$
• 对于其他顶点 $u$：
  • 如果 $\frac{w_u}{c_u} > \frac{b}{a}$，则该顶点不可能出现在最优路径中（因为 $i$ 是性价比最高的）
  • 否则，考虑在 $u$ 点购买卡牌后的转移：$$g(i, u, (x + c_u) \bmod a, 0/1) = \max(\dots, g(i, u, x, 0/1) + w_u - \left\lfloor\frac{x + c_u}{a}\right\rfloor \cdot b) $$
  • 移动转移：$g(i, v, x, 0/1) = \max(g(i, v, x, 0/1), g(i, u, x, 0/1))$

复杂度：$O(m \cdot n \cdot \max(c))$，因为 $x$ 只取 $0$ 到 $a-1$。

查询时：

$$\text{ans} = \max_{i=1}^n \left( g(i, p, r \bmod c_i, 1) + \left\lfloor\frac{r}{c_i}\right\rfloor \cdot w_i \right) $$

其中 $g(i, p, r \bmod c_i, 1)$ 表示必须经过顶点 $i$（因为 $i$ 是性价比最高的顶点）。

算法流程

1. 预处理：

   • 计算 $\text{magic} = \max(c_i)^2$
   • 运行小 $r$ DP：$O(m \cdot \text{magic})$
   • 运行大 $r$ DP：$O(m \cdot n \cdot \max(c))$

2. 处理查询：

   • 若 $r \le \text{magic}$：输出 $f(p, r)$
   • 否则：枚举 $i$，计算最大值并输出

时间复杂度

• 预处理：$O(m \cdot \max(c)^2 + m \cdot n \cdot \max(c))$
• 每次查询：$O(n)$
• 总复杂度：$O(m \cdot \max(c)^2 + m \cdot n \cdot \max(c) + q \cdot n)$

由于 $n \le 200$，$m \le 2000$，$\max(c) \le 200$，$q \le 2 \times 10^5$，该复杂度可行。

空间复杂度

• $f$ 数组：$O(n \cdot \max(c)^2) \approx 200 \times 40000 = 8 \times 10^6$
• $g$ 数组：$O(n \cdot n \cdot \max(c) \cdot 2) \approx 200 \times 200 \times 200 \times 2 = 1.6 \times 10^7$
• 均在内存限制内。

代码实现要点

1. 使用 $-\infty$ 初始化 DP 数组（代码中用 0xcfcfcfcfcfcfcfcf）
2. 对于大 $r$ DP，利用周期性优化（根据 $\gcd(c_u, a)$ 分组）
3. 注意处理未到达顶点 $i$ 的情况（$0/1$ 标记）
4. 使用 long long 存储威力值（可达 $10^9 \times 10^4 = 10^{13}$）

总结

本题的核心在于：

1. 引理：最优解中特殊卡牌数量有限
2. 分治：将 $r$ 的大小分成两种情况处理
3. 模运算优化：利用模 $c_i$ 的余数进行状态压缩
4. 枚举性价比最高点：大 $r$ 时枚举所有可能的 $i$

这种将问题分解成两个子问题的方法，使得原本 $O(mn\max(c)^2)$ 的复杂度降到了可接受范围。