【资料图】

有两个人玩游戏，有 \(n\) 个石子，和一个长度为 \(k\) 的序列，每次可以取 \(a_i\) 个但前提是剩下来的石子数有 \(a_i\) 个，第一个人先取，问两边都是用最优策略时，第一个人最多能得多少个石子。

可以设计状态 \((x, y, f)\) 表示第一个人取了 \(x\) 个石子，第二个人取了 \(y\) 个石子，由第 \(f + 1\) 人开取，显然 \(x + y \le n\)。

那么可以优化状态，因为要求的是第一个人最多能得多少个石子，所以可以将其中一个变量提取出来变成最优属性，可是光靠知道另一个人取了多少个石子是不够的，所以可以将它变成一共已经取了 \(x\) 个石子，还有由于两个人都用的是最优策略，所以 \(f\) 可以优化掉，也就变成了 \(dp_x = y\)，那转移就是 \(dp_x = \max(x - dp_{x - a_i})\)。

#include using namespace std;const int MaxN = 110, MaxV = 1e4 + 10;int dp[MaxV], a[MaxN], n, k;int main() {  cin >> n >> k;  for (int i = 1; i <= k; i++) {    cin >> a[i];  }  for (int i = 0; i <= n; i++) {    for (int j = 1; j <= k; j++) {      if (i >= a[j]) {        dp[i] = max(dp[i], i - dp[i - a[j]]);      }    }  }  cout << dp[n] << endl;  return 0;}