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。[代码](https://codeforces.com/contest/1628/submission/143660616)。 对于 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$ 的情况，时间复杂度线性。[代码](https://codeforces.com/contest/1628/submission/143665114)。