CF729F Financiers Game 题解

简单小 dp。设 $f_{i,j,k,0/1}$ 表示当前在左侧取到了 $i$ 右侧取到了 $j$ 位置上一次选了 $k$ 个石子，当前是先手/后手操作。那么 $O(n^3)$ 的 dp 是显然的。

考虑经典套路优化：容易观察到 $k$ 每一次最多 $+1$，也就是 $k$ 最大是 $O(n^{0.5})$ 级别的，因此 dp 可以优化到 $O(n^{2.5})$。然后又因为先后手是轮流操作的，所以先手和后手在一轮操作中最多产生 $1$ 的石子取数差异，在 $O(n^{0.5})$ 轮中先后手选择的石子差异数最多为 $O(n^{0.5})$。因此在 dp 中去掉 $j$ 的维度，转而记录 $j-i$ 的值（显然有 $0\le j-i\le k$），时间复杂度为 $O(n^2)$ 可以通过。