P5299 [PKUWC2018] Slay the Spire

洛谷：P5299 [PKUWC2018] Slay the Spire

LOJ：#2538. 「PKUWC2018」Slay the Spire

前言：请分清楚使用和抽取。九条要抽取 \(m\) 张牌，但只会使用 \(k\) 张牌。

首先考虑当抽出的 \(m\) 张牌确定时的策略：记 \(m\) 张牌中强化牌的数量为 \(c\)。

贪心策略是：使用强化牌至少使伤害翻一倍，一定不劣于使用一张攻击牌。

若 \(c < k - 1\)：强化牌全部使用，并优先使用，再使用 \(k - c\) 张数值较大的攻击牌。
若 \(c \ge k - 1\)：先使用 \(k - 1\) 张数值较大的强化牌，再使用 \(1\) 张数值最大的攻击牌。

也就是说，在最优策略下，九条使用的强化牌一定是数值前 \(w_1\) 大的，使用的攻击牌一定是前 \(w_2\) 大的。

对攻击牌和强化牌按数值从大到小排序后分别进行 DP，再组合起来计数。由于还要考虑到有些牌被抽取但并未被使用，因此我们想要的 DP 状态中应该包含 “使用到了哪张牌” 的信息。如果最终使用到了第 \(x\) 张牌，则 \(x\) 之前的未被选择的牌也一定未被抽取；而 \(x\) 之后的的牌的抽取情况，可以通过组合数算出。

具体地，记 \(f_{i, j}\) 表示考虑前 \(i\) 张强化牌，第 \(i\) 张必使用，共使用 \(j\) 张牌的数值乘积之和；记 \(g_{i, j}\) 表示考虑前 \(i\) 张攻击牌，第 \(i\) 张必使用，共使用 \(j\) 张牌的数值和之和。

直接做不方便转移，于是我又记 \(f^{'}_{i, j}\) 表示考虑前 \(i\) 张强化牌，共使用 \(j\) 张牌的数值乘积之和； \(g^{'}_{i, j}\) 表示考虑前 \(i\) 张攻击牌，共使用 \(j\) 张牌的数值和之和。

转移是容易的：

\[\begin{aligned} f^{'}_{i, j} &\leftarrow f^{'}_{i - 1, j} \\ f^{'}_{i, j + 1} &\leftarrow f^{'}_{i - 1, j} \times a_i \\ f_{i, j + 1} &\leftarrow f^{'}_{i - 1, j} \times a_i \\ \\ g^{'}_{i, j} &\leftarrow g^{'}_{i - 1, j} \\ g^{'}_{i, j + 1} &\leftarrow g^{'}_{i - 1, j} + \binom{i - 1}{j}\times b_i \\ g_{i, j + 1} &\leftarrow g^{'}_{i - 1, j} + \binom{i - 1}{j}\times b_i \\ \end{aligned} \]

注意 \(g\) 的转移时要给之前的每一个选取方案都加上一个 \(b_i\)。

对 \(c < k - 1\) 和 \(c \ge k - 1\) 分别计数：

\(c < k - 1\) 时：被抽取但未被使用的牌一定是攻击牌。

\[\begin{aligned} ans \leftarrow f_{i, j} \times g_{x, k - j} \times \binom{n - x}{m - k} \end{aligned} \]
其中 \(i\) 可以对每个 \(j\) 预求和优化掉。
\(c \ge k - 1\) 时：被抽取但未被使用的牌既可能是攻击牌，也可能是强化牌。

\[\begin{aligned} ans \leftarrow f_{i, k - 1} \times g_{x, 1} \times \binom{(n - i) + (n - x)}{m - k} \end{aligned} \]