M28970: 预测赢家

dp, http://cs101.openjudge.cn/practice/28970/

给定一个整数数组nums，玩家 1 和玩家 2 基于这个数组设计了一个游戏。

玩家1和玩家2轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即首个数组元素或者末尾的数组元素），取到的数字将会从数组中移除（数组长度减1）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。

如果玩家 1 能成为赢家，返回true。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回true。你可以假设每个玩家的玩法都会使他的分数最大化。

输入

第一行为测试组数n（n ≤ 350）

后面n行为数组初始元素个数m 与 m个元素

1 ≤ m ≤ 20， 0 ≤ nums[i] ≤ 10^7

输出

对于每一组测试数据，输出true 或 false

样例输入

7
3 1 5 2
4 1 5 233 7
5 242 353 531 22 231
8 231 343 63 543 54 332 541 674
3 423 552 653
11 231 343 63 543 54 332 541 674 423 552 653
6 1 1 1 1 1 1

样例输出

false
true
false
true
true
false
true

提示

来源

2024-TA-xjk

这是一个经典的 博弈类动态规划 问题，通常被称为 “预测赢家”（Predict the Winner）。我们可以使用 记忆化递归 或 区间 DP 来解决。

核心思想

每个玩家都采取最优策略。
我们关心的是：玩家1是否能获得 ≥ 玩家2 的分数。
等价于：玩家1的得分 - 玩家2的得分 ≥ 0

定义一个函数 diff(i, j) 表示在子数组 nums[i:j+1] 中，当前玩家（无论是谁）能比对方多得的最大分数。

如果当前玩家拿 nums[i]，那么对手会在 [i+1, j] 中玩，此时当前玩家的优势是：
```
nums[i] - diff(i+1, j)
```
如果当前玩家拿 nums[j]，那么对手会在 [i, j-1] 中玩，此时当前玩家的优势是：
```
nums[j] - diff(i, j-1)
```

所以状态转移方程为：

diff(i, j) = max(nums[i] - diff(i+1, j), nums[j] - diff(i, j-1))

边界条件：当 i == j 时，diff(i, j) = nums[i]

最终我们只需要判断 diff(0, n-1) >= 0 是否成立。

Python 实现（带缓存）

python

import sys
from functools import lru_cache

def can_player1_win(nums):
    n = len(nums)
    
    @lru_cache(maxsize=None)
    def diff(i, j):
        if i == j:
            return nums[i]
        return max(nums[i] - diff(i + 1, j), nums[j] - diff(i, j - 1))
    
    return diff(0, n - 1) >= 0

# 主程序读取输入
input = sys.stdin.read
data = input().split()

t = int(data[0])
index = 1
results = []

for _ in range(t):
    m = int(data[index])
    index += 1
    nums = list(map(int, data[index:index + m]))
    index += m
    results.append("true" if can_player1_win(nums) else "false")

# 输出结果
for res in results:
    print(res)

🔍 示例解释

以第一个样例 3 1 5 2 为例：

数组是 [1, 5, 2]
玩家1先手，无论怎么选，玩家2都能拿到更高的总分（比如玩家1选1，玩家2选5，玩家1只能拿2 → 1+2=3 vs 5）
所以输出 false

⏱️ 时间复杂度

每个测试用例最多有 $ m \leq 20 $
区间 DP 状态数为 $ O(m^2) $，每个状态计算 $ O(1) $
总体非常高效，适用于题目限制

M28970: 预测赢家 ​

M28970: 预测赢家