题解：P12159 [蓝桥杯 2025 省 Java B] 数组翻转

· · 题解

蒟蒻的我第一次在洛谷写题解(上一次的寄了)，还请多包涵不足的地方。

问题描述。 给定长度为 n 的正整数数组 a_1,a_2,\dots,a_n。小明可以先对数组中任意一段区间 [l,r] 做一次翻转（左右颠倒），然后从翻转后的数组中选取一段所有元素相等的子数组获得得分，若选取的区间长度为 L，元素值为 v，则得分为 L\times v。问小明能获得的最大得分。

样例说明。
样例输入： 

7  
4 4 3 3 2 1 3

翻转区间 [5,7] 后数组变为 4,4,3,3,3,1,2，此时选取那 3 个连续的 3，可得分数 3\times 3=9，为最优。

关键观察。
翻转操作的唯一作用，是可以将原数组中相同值 v 的两段不相邻的连续区间调换位置，使它们在翻转后相邻，从而合并为一段更长的相同值区间。
若不翻转，则对于值 v，只能获取它在原数组中某一段最大连续长度 L_{\max}，得分为 L_{\max}\times v。
若允许一次翻转，则对于每个值 v，可以选择原数组中两段连续且值都为 v 的区间，其长度分别为 L_1,L_2，通过翻转把它们拼接到一起，获得长度 L_1+L_2 的区间，得分为 (L_1+L_2)\times v。最优情况下，对于每个 v，应选其最长的两段连续区间。

算法实现。

  1. 使用一次从左到右的扫描。
  2. 令 per[i] 表示以位置 i 为结尾的、且值相同的最长连续段的长度。
  3. 当 a_i=a_{i-1} 时，per[i]=per[i-1]+1；否则，表示一段结束，将该段长度 per[i-1] 记入哈希表 mp[a_{i-1}]，更新此值的「第一长」和「第二长」；然后重置 per[i]=1。
  4. 扫描结束后，哈希表 mp[v] 中存有值为 v 的所有连续段的「第一长」 f_1 和「第二长」 f_2。对每个键值对 (v,(f_1,f_2))，计算得分 v\times(f_1+f_2)，取最大。
  5. 时间复杂度 O(n)，空间复杂度 O(n)（用于存储 per 数组与哈希表）。

代码如下。 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll N = 1e6 + 5;

void solve(){
    int n;
    cin >> n;
    vector<ll> a(n+5), per(n+5);
    map<int, pair<ll, ll>> mp;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= n + 1; i++) {
        if (a[i] == a[i - 1]) {
            per[i] = per[i - 1] + 1;
        } else {
            per[i] = 1;
            auto &[firs, seco] = mp[a[i - 1]];
            if (per[i - 1] > firs) {
                seco = firs;
                firs = per[i - 1];
            } else {
                seco = max(seco, per[i - 1]);
            }
        }
    }

    ll ans = 0;
    for (auto [x, pa] : mp) {
        auto [firs, seco] = pa;
        ans = max(ans, x * (firs + seco));
    }

    cout << ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析。

这样就能在 n \le 10^6 时依然保持线性通过。