CF1628D2 Game on Sum (Hard Version)

· · 题解

对于 Easy version，n,m \leq 2\times 10 ^ 3。由于我们 只关心游戏进行的轮数以及 Bob 使用 add 的次数，考虑设计 DP：设 f_{i, j} 表示经过 i 轮后 Bob 用了 j 次 add，Alice 所能达到的最大分数，但是不方便转移，因为两人绝顶聪明使得当前决策 仅 基于接下来的决策。

综上，可以发现一般博弈论的 DP 题都是 从后往前 DP，即从确定的终止状态向初始状态 DP，因为 绝顶聪明 这一条件使得双方都能预测到他们当前的行为对后续局面的影响，可以说只有 后效性 而没有 前效性：若 i, j 确定，则两人之前的决策对当前决策无影响。

因此，设 f_{i, j} 表示游戏还剩 i 轮，Bob 还需使用 j 次 add 时，Alice 还能获得的最大分数（另一种理解方法是当 n = i, m = j 时的答案）。转移即考虑 Alice 选择的数 x\in [0, k] 以及 Bob 选择加还是减（外层取 \min），有 f_{i, j} = \min(f_{i - 1, j - 1} + x, f_{i - 1, j} - x)。由于 Alice 需要让分值最大，所以当 x = \dfrac {f_{i - 1, j - 1} - f_{i - 1, j}} 2 时，f_{i, j} 取到最大值 \dfrac{f_{i - 1, j - 1} + f_{i - 1, j}}2，这就是转移方程。

边界值：f_{i, 0} = 0\ (0\leq i\leq n)，以及 f_{i, i} = i\times k\ (0\leq i\leq m)，转移仅在 1\leq j < i \leq n, j\leq m 之间进行。时间复杂度 nm，可以通过 Easy version。代码。

对于 Hard version，考虑每个 f_{i, i} 对答案的贡献：从 f_{i, i}\to f_{n, m}，一共进行了 n - i 次除以 2，同时，它被计算到的次数相当于 (i + 1, i) 走到 (n, m)，每次向 x + 1, y+ 1 或 x + 1, y，即右或右上方向走的路径数量。不是 (i, i) 的原因是 f_{i, i} 无法转移到 f_{i + 1, i + 1}，它是边界值，转移仅在 j < i 时进行。在 n - i - 1 步中选 m - i 步进行纵坐标加 1，方案数为 \dbinom{n - i - 1}{m - i}。综上，答案为：

k\sum_{i = 1} ^ m \dfrac{i\times \binom {n - i - 1}{m - i}}{2 ^ {n - i}}

注意特判 n = m 的情况，时间复杂度线性。代码。