题解 | #宵暗的妖怪#

• 状态定义
  设 dp[i] 为 只考虑第 i 个位置（即 a[1] 到 a[i]） 时，能够得到的最大饱食度。
  由于区间长度为 3，若在第 i 个位置结束一个区间，则该区间必覆盖 i‑2、i‑1、i 三个位置，贡献的饱食度为 a[i‑1]（区间的中点）。

• 状态转移
  对第 i 个位置有两条决策：

  1. 不使用以 i 结尾的区间：此时 dp[i] = dp[i‑1]（直接把第 i 段留空）。
  2. 使用以 i 结尾的区间：此时必须把 i‑2、i‑1、i 三段全部占用，之后只能考虑 i‑3 之前的位置。于是
     dp[i] = dp[i‑3] + a[i‑1]（这里的 a[i‑1] 正是区间的中点值）。

  取两者中的较大者即可得到前 i 位的最优值：

dp[i] = max(dp[i‑1], dp[i‑3] + a[i‑1]) （i ≥ 3）

• 初始状态
  若 i < 2，根本不足以形成任何区间，饱食度只能是 0：

dp[0] = dp[1] = 0, dp[2] = a[1]

• 答案
  dp[n-1] 即为整条道路的最大饱食度。

• 空间优化
  递推只涉及 dp[i‑1]、dp[i‑2]、dp[i‑3]，因此不必保存整个数组，只需用三个滚动变量即可实现 O(1) 额外空间。

• 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    vector<ll> dp(n);
    dp[0] = dp[1] = 0;
    dp[2] = a[1];

    for (int i = 3; i < n; i++) {
        // 1. 不进行以 a[i] 为右边界的操作
        ll option1 = dp[i - 1];

        // 2. 进行以 a[i] 为右边界的操作 (a[i-2], a[i-1], a[i])
        //    获得的饱食度是中间部分 a[i-1] 的值。
        //    上一个独立操作的右边界在 i-3 结束。
        ll option2 = dp[i - 3] + a[i - 1];

        dp[i] = max(option1, option2);
    }
    cout << dp[n - 1] << endl;
}