牛客小白月赛110 —— D 智乃与长短期主义者博弈 python 补题 + 题解

智乃与长短期主义者博弈

题目描述

在博弈游戏中，往往存在长期主义者、短期主义者两种角色
短期主义者就像是一个贪婪无比的短视地精，他只会选择当前步骤中所有局部选择的最优解
长期主义者就好比一个经验丰富的千层饼，他总会选择在每个步骤中选择能达到全局最优的决策，哪怕对于当前阶段可能是亏损的
显然，长期主义者是否明知对方的行动模式，对于他构建自己的全局最优决策存在非常大的影响
在本题中，长期主义者将被明确告知短期主义者的行动模式，他将以此作为已知条件构建他的最优决策

现在有这样一个游戏，有n个整数排成一排，两个人轮流取数，每次只能从两端的数字中选择一个取走

例如一开始有3个数字为1,3,2 则一开始只能拿1或者2，只有当1或者2被取走后才能拿到中间的3

短期主义者总是选择两端中较大的数字，并且如果两数相同，则选择最左端的数字，而长期主义者（已知对方的行动模式）总是选择对于全局最优的决策

两人均以最大化自己的得分为目标，假设短期主义者先手，则最终二者博弈的得分各自是多少？

输入描述:

第一行输入一个正整数 $n$ (1≤ $n$ ≤1000)表示整数的个数

接下来另起一行，输入 $n$ 个正整数 $a_i$ (1≤ $a_i$ ≤1e6 )表示这一排整数的内容

输出描述:

在一行内输出两个整数，分别表示短期主义者、长期主义者的得分，整数之间用一个空格隔开

示例输入1

6
1 100 1 100 1 100

示例输出1

300 3

示例输入2

7
4 5 7 6 2 3 1

示例输出2

14 14

解题思路：

为了理解并解决这个问题，我们需要明确长期主义者和短期主义者的策略，并使用区间DP来计算他们的得分。

【算法】动态规划专题⑪ —— 区间DP python

问题分析

短期主义者的策略：
- 总是选择两端中较大的数字。
- 如果两数相同，则选择最左端的数字。
长期主义者的策略：
- 已知对方的行动模式，总是选择对全局最优的决策。
- 目标是最大化自己的得分。
博弈过程：
- 两人轮流取数，每次只能从两端的数字中选择一个取走。
- 短期主义者先手。

具体步骤

定义一个二维DP数组 dp[i][j] 表示在区间 [i, j] 内长期主义者能够获得的最大得分。
为了简化问题，我们还需要记录整个序列的总和，以便计算短期主义者的得分。

初始化：
- 对于长度为1的子序列，长期主义者无法得分（因为短期主义者先手），所以 dp[i][i] = 0。
- 对于长度为2的子序列，长期主义者可以取较小的那个数，因此 dp[i][i+1] = min(a[i], a[i+1])。
状态转移方程：
- 对于每个长度大于等于3的子序列 [i, j]，我们需要考虑两种情况：
  - 如果短期主义者选择了左边的数 a[i]，那么长期主义者可以选择 a[j] 或者 a[i+1]。
  - 如果短期主义者选择了右边的数 a[j]，那么长期主义者可以选择 a[i] 或者 a[j-1]。

code如下：

n = int(input())
a = list(map(int, input().split()))
dp = [[0] * n for _ in range(n)]
# dp[i][j]:长期主义者最大得分for i in range(n):  # 初始化dp[i][i] = 0if i < n - 1:dp[i][i + 1] = min(a[i], a[i + 1])
for len in range(3, n + 1):for i in range(n - len + 1):j = i + len - 1if a[i] >= a[j]:dp[i][j] = max(dp[i + 1][j - 1] + a[j], dp[i + 2][j] + a[i + 1])else:dp[i][j] = max(dp[i + 1][j - 1] + a[i], dp[i][j - 2] + a[j - 1])print(sum(a) - dp[0][n - 1], dp[0][n - 1])