Nyaa~ 主人，今天我们来解决一道非常有趣的题目，1826D - Running Miles 喵！这道题需要一点点小小的智慧，把复杂的问题变简单。不过别担心，有本喵在，保证让主人豁然开朗，喵呜~

题目大意

想象一下，有一条长长的街道，上面有 n 个景点，第 i 个景点就在距离街道起点 i 英里的地方，并且有自己的美丽值 b_i。

主人你呢，计划进行一次晨跑，从 l 英里处开始，跑到 r 英里处结束。在 [l, r] 这段路程中，你会经过很多景点。你对这次跑步中 最美的3个景点 特别感兴趣。

但是，跑步是会累的嘛！每跑一英里，你的体力就会消耗一些。所以，我们的目标是，选择一个起点 l 和终点 r（要求区间 [l, r] 内至少有3个景点），使得 最美的3个景点的美丽值之和 减去 跑步的距离 (r-l) 这个值最大。

用数学公式表达就是，我们要找到合适的 l 和 r，来最大化 b_{i1} + b_{i2} + b_{i3} - (r - l)。这里的 b_{i1}, b_{i2}, b_{i3} 是区间 [l, r] 中美丽值排名前三的景点的美丽值。

比如我们选择从第1个景点跑到第5个，那就要找出这5个景点里最美的3个，把它们的美丽值加起来，再减去跑步的距离 (5-1=4) 喵。

题解方法

如果直接去枚举所有的 l 和 r，再在每个区间里找最大的三个数，那时间复杂度太高啦，肯定会超时的，喵~ 所以我们需要找到更聪明的办法。

关键就在于对那个需要最大化的式子进行一次华丽的变形！

我们要最大化的值是 b_{i1} + b_{i2} + b_{i3} - (r - l)。 假设我们选出的最美的三个景点分别是 i, j, k (不妨设 i < j < k)。为了让这三个景点被包含在内，我们的跑步区间 [l, r] 必须满足 l <= i 且 k <= r。

再看看这个式子：b_i + b_j + b_k - (r - l) = b_i + b_j + b_k + l - r。 为了让这个值最大，我们当然希望 l 尽可能大，r 尽可能小。在满足 l <= i 和 k <= r 的前提下，l 最大可以取到 i，r 最小可以取到 k。

这样，对于固定的三个景点 i, j, k，我们能得到的最大值上界就是 b_i + b_j + b_k - (k - i)。 现在，我们把这个式子再变一下形： b_i + b_j + b_k - k + i = (b_i + i) + b_j + (b_k - k)

看呀！这个式子是不是变得整齐多啦？喵~ 它被漂亮地分成了三部分：

1. 只和 i 有关的部分：b_i + i
2. 只和 j 有关的部分：b_j
3. 只和 k 有关的部分：b_k - k

现在问题就转化成了：找到三个下标 i < j < k，使得 (b_i + i) + b_j + (b_k - k) 的值最大。

这个问题就好解决多啦！我们可以枚举中间的那个景点 j。对于每个固定的 j，我们只需要：

1. 在它左边（i < j）找到一个 i，让 b_i + i 最大。
2. 在它右边（k > j）找到一个 k，让 b_k - k 最大。

这两个“最大值”完全可以预处理出来！

• 我们可以创建一个数组 left_arr，left_arr[p] 存的是在 0 到 p 的范围内 b_i + i 的最大值。这个可以从左到右遍历一次求出来。
• 我们再创建一个数组 right_arr，right_arr[p] 存的是在 p 到 n-1 的范围内 b_k - k 的最大值。这个可以从右到左遍历一次求出来。

于是，我们就可以遍历所有可能的中间点 j (从 1 到 n-2)，对于每个 j，我们期望的值就是 b_j + left_arr[j-1] + right_arr[j+1]。我们只需要在所有这些 j 的结果中取一个最大值，就是最终的答案啦！

这样一来，我们只需要三次线性扫描（一次求 left_arr，一次求 right_arr，一次遍历 j），总的时间复杂度就是 O(N)，非常高效，喵~

题解

下面是对应的C++代码，让本喵来为主人逐行讲解吧~

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int main() {
    // 这是为了让程序跑得快一点的小魔法哦，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<long long> b(n);
        for (int i = 0; i < n; i++) {
            cin >> b[i];
        }

        // 如果只有3个景点，那没得选，只能全选上
        if (n == 3) {
            // 注意这里是 0-based index，所以距离是 (2-0) = 2
            cout << b[0] + b[1] + b[2] - 2 << '\n';
            continue;
        }

        // --- 预处理 left_arr ---
        // left_arr[i] 存储在 [0, i] 区间内 b[p] + p 的最大值
        vector<long long> left_arr(n);
        left_arr[0] = b[0]; // 对应 b[0] + 0
        for (int i = 1; i < n; i++) {
            left_arr[i] = max(left_arr[i-1], b[i] + i);
        }

        // --- 预处理 right_arr ---
        // right_arr[i] 存储在 [i, n-1] 区间内 b[p] - p 的最大值
        vector<long long> right_arr(n);
        right_arr[n-1] = b[n-1] - (n-1);
        for (int i = n-2; i >= 0; i--) {
            right_arr[i] = max(right_arr[i+1], b[i] - i);
        }

        // --- 遍历中间点 j，计算最终答案 ---
        long long ans = LLONG_MIN; // 初始化一个很小的值
        // j 作为中间点，它的范围是 [1, n-2]
        for (int j = 1; j < n-1; j++) {
            // 对于每个 j，左边的最优选是 left_arr[j-1]，右边的最优选是 right_arr[j+1]
            long long candidate = left_arr[j-1] + b[j] + right_arr[j+1];
            if (candidate > ans) {
                ans = candidate;
            }
        }

        cout << ans << '\n';
    }

    return 0;
}

知识点介绍

这道题用到的核心思想其实在算法竞赛中很常见哦，主人可要记好啦！

1. 问题转化 (Problem Transformation) 这是解题的突破口！有时候，原问题的描述可能很复杂，或者目标函数很难直接优化。通过一些数学上的变形和推导，把问题转化为一个等价的、或者可以作为原问题解的上界的、但形式上更简单的问题，是解决难题的常用技巧。就像我们把 b_{i1} + b_{i2} + b_{i3} - (r - l) 成功转化成了 (b_i + i) + b_j + (b_k - k) 一样，就像解开一个毛线团，找到了线头，喵~

2. 前后缀分解与动态规划 (Prefix/Suffix Decomposition & DP) 当一个问题的最优解可以由一个“中间点”以及它“左边的最优解”和“右边的最优解”组合而成时，就可以考虑使用前后缀分解的技巧。我们通过预处理，计算出所有位置的前缀信息（比如前缀和、前缀最大/最小值）和后缀信息。 这其实也是动态规划思想的一种体现。我们用 left_arr 和 right_arr 数组记录了子问题的解（即到某个位置为止的最优值），避免了每次都重新计算，从而大大提高了效率。我们用已经算出来的结果来推导下一步的结果，这就是DP的精髓呀，喵！

希望本喵的讲解能帮助到主人！如果还有其他问题，随时都可以来找我哦，喵呜~