博弈论选做

CF388C

简要题意

两个人博弈，有 堆牌，每堆牌有 张，每张牌上面有非负数分数。两人轮流行动。A 每次可以从任意一堆非空牌堆中取走最上方的一张牌，B 可以取走最下面的一张牌，若两人都按最优方案行动（使自己的得分最大），求两人最终的得分。

思路

注意到本题一个人取上面另一个人取下面，猜测只有一小部分是需要博弈的，剩余都是固定分配的。

实际上，只有奇数张牌的牌堆的中间那张是需要争夺的，其余一定是上面一半归 A 下面一半归 B。

证明

参考 bot 的证明方法，我们设需要证明的局面为结果局面（即一个人拿上半，另一个人拿下半，暂不考虑奇数堆）。

若每堆张数都是偶数，那么两人都有办法迫使局面成为结果局面。

具体来说，如果 B 要迫使局面成为结果局面，操作应是如下：

• A 拿任意一堆的堆顶的牌；
• B 拿相应堆堆底的牌。

如果 B 抽风在某一次 A 取完之后，B 取另一堆的牌，A 要使局面成为结果局面，按照上面的方法跟着 B 拿，拿到最后 B 将会剩下原来没有拿的那一堆牌有一张没有拿，同样变成结果局面。

考虑对于任意一个不是结果局面的局面，若得分不同，那么得分少的人一定不会希望来到这个局面，因此迫使局面成为结果局面，至于为什么无法得到比结果局面多的分，同样理解。

因此若只有偶数张牌的牌堆，最终局面是固定的。

接下来考虑奇数的情况。奇数的牌堆抽出一张牌过后，无论是谁抽出的，这个牌堆都变成了偶数张，那么只考虑这一堆的话，分配方案就固定了。

我们钦定一种选择方案，即如果当前还有奇数张牌的牌堆，则两人轮流选择一堆奇数张牌的牌堆，取出一张牌，将其变成偶数张牌的牌堆，若无奇数张牌的牌堆，则按照结果局面的情况分配。

考虑这个过程中可能出现的变数，即突然有一个人在仍然存在奇数牌堆的时候，选择一张偶数牌堆的牌取出。若这种情况可能得到比结果局面更好的分数，那么对手得分就少，因此会迫使局面变成结果局面，即选择同一堆牌堆中的牌。如果你很犟，非要去选偶数堆，那么对手一定会和你执行相同的操作，直到只剩下奇数堆。如果对手不跟你执行同一个操作，那么他一定有更好的收益，所以你得分就变少了，因此你不会做这个操作。

考虑选择奇数张牌的牌堆时如何贪心，因为选择一个堆取出牌，等价于将牌堆变成偶数张牌的牌堆，并且将原来中间的那张牌变成结果局面中自己的那张牌，然后转换先后手。所以整个过程等价于两人轮流选择一堆奇数张牌的牌堆，然后取走中间那张牌（感性理解和取走边上的牌是一样的，因为和取牌的顺序无关，只和牌的位置有关），直到仅剩下偶数张牌的牌堆，然后中间切开对半分即可。

P2964

简要题意

两个人博弈，有 个硬币排成一条线，每个硬币有价值 ，两人轮流从左边开始取硬币。一个人取的硬币数量必须在 ，范围内，其中 为上一个人上一次取硬币的数量，初始为 。问先手可以获得硬币价值的最大值。

思路

这题终结状态不是很好找，考虑逆推，设 表示从第 位开始取硬币，且上一个人上一次取了 个的最大收益。

取一次先后手互换，因此考虑用 到 的总硬币价值，减去下一轮先手取硬币的最大收益，得到当前的最大价值。

枚举 ，有转移方程：

其中 。

时间复杂度 ，考虑优化。我们发现在 相等时对于对每一个 求答案都要将 从头枚举一遍，这显然不优。观察到 中的式子和 无关，因此 和 的贡献来源大部分相同且无冲突，考虑用 转移 ，有式子：

时间复杂度 。