2786. 访问数组中的位置使分数最大

发表于 分类于 阅读次数： Waline： 本文字数： 997 阅读时长 ≈ 3 分钟

考点

  • 状态机DP
  • 初始值设置
  • 状态设计

一、题目核心规则抽象

给定数组 nums，从 下标 0 必须开始访问，每次可以跳到任意更大的下标：

  • 如果 相邻两次访问的数字奇偶相同：✅ 不扣分
  • 如果 奇偶不同：❌ 扣 x
  • 每访问一个位置，都会获得 nums[i] 分数

目标： \[ \text{最大化总得分} \]

二、奇偶区间（Parity Segment）建模思想

由于：

  • nums[i] > 0
  • 同奇偶不扣分

所以得到一个非常重要的结构性质：

✅ 在一段连续“同奇偶区间”里，一旦进入，就一定全部取完。

因此整个路径的真正“决策点”，只发生在：

🔥 奇偶发生切换的分界点

示例：奇偶区间拆分示意图

1
2
3
4
nums = [ 2, 4, 6 | 3, 9, 1 | 8, 10 ]
         E  E  E   O  O  O   E   E
         ↑        ↑        ↑
       分段1     分段2     分段3

在每个“段内”：

  • 一定是：

\[ \text{当前奇偶和} += nums[i] \]

只有在 段与段之间，才需要在： \[ \text{是否支付 } x \text{ 扣分} \;\; vs \;\; \text{是否切换奇偶} \] 做博弈选择。

三、 DP 状态定义

设： \[ \begin{aligned} even &= \text{当前处理到 i 为止，\textbf{最后一个访问的是偶数}的最大得分} \\ odd &= \text{当前处理到 i 为止，\textbf{最后一个访问的是奇数}的最大得分} \end{aligned} \] ⚠️ 特别注意：

  • even 和 odd 不是当前“区间和”
  • 而是：全前缀最优路径的结束状态

四、最关键的错误：初始化 = 0 是“伪路径”

一开始的错误初始化是：

1
2
3
4
if (nums[0] & 1)
    odd = nums[0], even = 0;
else
    odd = 0, even = nums[0];

这在数学上等价于：

❌ “存在一条合法路径： 没有经过 0，却已经以奇/偶结尾，得分为 0”

但题目规定：

✅ 必须从下标 0 开始访问

因此：

  • 如果 nums[0] 是偶数： \[ odd = -\infty \]

  • 如果 nums[0] 是奇数： \[ even = -\infty \]

这正是最终 AC 的修复：

1
2
3
4
if (nums[0] & 1)
    odd = nums[0], even = INT_MIN;
else
    odd = INT_MIN, even = nums[0];

❗ 错误初始化会导致什么后果？

会引入一条“从中间元素单独起跳”的非法路径：

例如：

1
2
even = 58
odd  = 0   ← 这是错误代码中的“伪路径”

当遇到一个奇数 65 时： \[ odd = \max(\underbrace{0 + 65}_{非法路径},\; 58 + 65 - 74) \] 结果错误选择了 65，而正确值应该是 49。 这正是 输出 486 而不是 470 的根本原因。

五、DP转移

现在 AC 的转移策略是：

① 非分界点（同奇偶）

1
2
3
4
if (nums[i] & 1)
    odd += nums[i];
else
    even += nums[i];

等价于数学式： \[ \text{段内累加}:\quad dp += nums[i] \] ✅ 因为同奇偶不扣分，且所有数为正，必取

② 分界点（奇偶切换）

最终 AC 的关键转移是：

1
2
3
4
if (nums[i] & 1)
    odd = max(odd + nums[i], even + nums[i] - x);
else
    even = max(even + nums[i], odd + nums[i] - x);

对应数学表达为：

当前是奇数：

\[ odd_i = \max \begin{cases} odd_{i-1} + nums[i] & \text{原本就在奇数段} \\ even_{i-1} + nums[i] - x & \text{刚从偶数段切换} \end{cases} \]

当前是偶数：

\[ even_i = \max \begin{cases} even_{i-1} + nums[i] & \text{原本就在偶数段} \\ odd_{i-1} + nums[i] - x & \text{刚从奇数段切换} \end{cases} \]

✅ 这一层的本质含义：

在“奇偶分界点”，做的是：

  • 继续原奇偶 → 不扣 x
  • 切换奇偶 → 扣一次 x

六、代码结构

1
2
3
4
5
6
7
8
9
10
11
12
初始化：
even = (nums[0] 是偶数 ? nums[0] : -∞)
odd  = (nums[0] 是奇数 ? nums[0] : -∞)

for 每个 i 从 1 到 n-1:
    如果 nums[i] 与 nums[i-1] 奇偶相同:
        段内累加
    否则:
        在“继续原奇偶” 和 “切换奇偶扣 x” 中取 max

答案：
max(even, odd)

七、AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    static const int maxn = 1e5 + 5;
    long long maxScore(vector<int>& nums, int x) {
        long long odd, even;
        if (nums[0] & 1)
            odd = nums[0], even = INT_MIN;
        else
            odd = INT_MIN, even = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            // 是分界点
            if ((nums[i] & 1) && (nums[i - 1] & 1) == 0 ||
                ((nums[i] & 1) == 0) && (nums[i - 1] & 1)) {
                if (nums[i] & 1)
                    odd = max(odd + nums[i], even + nums[i] - x);
                else
                    even = max(even + nums[i], odd + nums[i] - x);
            } else {
                if (nums[i] & 1)
                    odd += nums[i];
                else
                    even += nums[i];
            }
        }
        return max(even, odd);
    }
};