题目：AT_abc_270_d
链接：洛谷, AT，vjudge

题意

• 有两个人轮流取石子，有 \(n\) 颗石子和长度为 \(k\) 的数组 \(a\)，每次取石子的人可以取走 \(a_i\) 颗石子，当然当时剩下的石子数量要 $ \ge a_i$ 才行，若二人都走最优策略，那么先手可以取走都少颗棋子？

• 数据范围：\(1 \le n \le 10^4, 1 \le k \le 100\)。

思路

暴搜

• 首先我们可以写一个暴力搜索，状态为 \((x, y, 0 / 1)\) 表示取走了 \(x\) 颗棋子，先取石子的人取了 \(y\) 颗，当前位谁取石子(定义 \(1\) 为先手，\(0\) 为后手)。

• 那么有转移：\((x,y,f) -> (x + a_i, y + a_i \cdot f, f \oplus 1)(1 \le i \le n)\)。

• 时间复杂度

  • 状态数：\(O(n^2)\)。
  • 转移数：\(O(n^2k)\)。
  • 总时间复杂度：\(O(n^2k)\).

正解

• 其实这是个博弈题。令 \(dp_{i,f}\) 表示一共取了 \(i\) 个石子，当前操作为 \(f\) 取石子，\(f\) 能得到的最大石子数，那么 \(dp_{i,f} = \max\limits_{j = 1}^k \{x - a_j - dp_{x - a_j}\} = \max\limits_{j = 1}^k \{x - dp_{x - a_j}\}\)。

• 所以就结束了，但是这个题还有更简单的实现方式，因为两个人都实现的最优策略，所以无需分前后手，可以直接省略后面一维。

• 时间复杂度

  • 状态数：\(O(n)\)。
  • 转移数：\(O(nk)\)。
  • 总时间复杂度：\(O(nk)\)。