问题分析

本题是一道基于区间动态规划（DP） 的博弈问题，核心任务是模拟两人轮流从序列两端取数的过程，计算双方的最优得分。每个数字有其首次出现位置（d数组）和末次出现位置（c数组），取数时若满足特定条件可获得分数，最终需输出双方的最大得分比。

算法思路

1. 预处理数组

• d[x]：记录数字x在序列中首次出现的位置。
• c[x]：记录数字x在序列中末次出现的位置。
• 这两个数组用于判断取数时是否满足得分条件。

2. 得分判定函数（cost）

判断在区间[l, r]中取位置x的数字是否能得分：

• 若x是数字a[x]的首次出现位置（x == d[a[x]]），且区间右端点r不小于该数字的末次出现位置（r >= c[a[x]]），则得1分。
• 若x是数字a[x]的末次出现位置（x == c[a[x]]），且区间左端点l不大于该数字的首次出现位置（l <= d[a[x]]），则得1分。
• 否则得0分。

3. 区间DP状态定义

• dp[l][r][turn]：表示在区间[l, r]中，当前轮到turn（0或1，代表两位玩家）取数时，当前玩家能获得的最大得分，以及另一玩家的对应得分。
  • dp[l][r][0]：玩家0的最大得分。
  • dp[l][r][1]：玩家1的最大得分。

4. DP状态转移

• 边界条件：当区间长度为1（l == r）时，当前玩家只能取该位置的数，得分由cost函数判定，另一玩家得0分。
• 递归转移：对于区间[l, r]，当前玩家有两种选择：
  1. 取左端点l：得分 = 左半区间[l+1, r]中另一玩家的状态得分 + 当前取l的得分（cost(l, r, l)）。
  2. 取右端点r：得分 = 右半区间[l, r-1]中另一玩家的状态得分 + 当前取r的得分（cost(l, r, r)）。
• 选择策略：
  • 若两种选择得分不同，取得分更高的选项，另一玩家得分对应更新。
  • 若得分相同，取另一玩家得分更小的选项（保证当前玩家最优的同时，最小化对手得分）。

5. 结果输出

最终答案为dp[1][n][0] : dp[1][n][1]，即玩家0和玩家1在整个区间[1, n]上的最优得分比。

关键复杂度分析

• 时间复杂度：区间DP的状态总数为O(n^2 * 2)（n为序列长度，2代表两位玩家），每个状态的计算涉及两次递归调用和常数次操作，故总复杂度为O(n^2)。
• 空间复杂度：DP数组存储所有区间和玩家状态，空间复杂度为O(n^2)，适合n <= 3000的规模。

代码解析

算法的核心是通过区间DP模拟博弈过程，利用递归和记忆化存储避免重复计算，确保双方在每一步都做出最优选择，最终得到全局最优的得分比。