CF729F Financiers Game

题意 ：两个人（A 与 B）分别从长度为 的数列两端开始取数，如果前一个人取了 个数，后一个人必须取 或 个，第一个人最开始可以取 个或 个，不能操作时结束。

A 想要最大化 A 选的数的和减去 B 选的数的和。B 想要最小化这个值。

两人均采取最优策略，求最终结果。

，时限 ，空限 。

---

简单博弈论。

设 表示 A 取了 个数， B 取了 个数，上一步取了 个数，是 A/B 方操作，这样之后能得到的 A 选的数的和减去 B 选的数的和。

在 A 操作的回合，其会选择权值最大的转移， B 则会选择权值最小的转移。

状态量是 的，转移 ，复杂度为 。

不难发现 这一维不超过 ，且 不超过 。

这样状态量就是 级别的了，直接记忆化搜索即可通过。

需要精细分析数组大小。

假设游戏（来回）轮数为 。

具体而言，在极端情况下，若 A 每次都比 B 多拿一个，则拿取总数为 则 ，所以 。

在极端情况下，若每次都比对方多拿一个，则拿取总数为 则 ，所以 。