染色

问题概要

给你一个长为 \(n\) 的正整数序列 \(A = (A_1, \dots, A_n)\)，从左到右排成一行。

你要将 \(A\) 的每个元素染成红色或蓝色，然后按下述方式计算每个 \(A_i\)（\(1 \le i \le n\)）的得分：

• 如果 \(A_i\) 左侧没有与它同色的数，则 \(A_i\) 的得分为 \(0\)。若有，设它左侧与它最近的同色元素为 \(A_j\)。若 \(A_i = A_j\) 则 \(A_i\) 的得分为 \(A_i\)，否则 \(A_i\) 的得分为 \(0\)。

求对序列 \(A\) 的一个染色方案中，\(A\) 的元素的得分之和可能达到的最大值。

你需要解决 \(T\) 组测试。

• \(1 \le T \le 10\)
• \(2 \le n \le 2 \times 10^5\)
• \(1 \le A_i \le 10^6\)

换个说法

把序列 \(A\) 切成若干段，然后按下述方式计算计算每个 \(A_i\) 的得分：

• 若 \(A_i\) 是一段的第一个数，则 \(A_i\) 有分当且仅当它和上上一段最后一个数相等，否则 \(A_i\) 有分当且仅当 \(A_i = A_{i-1}\)。

思路

考虑序列 \(a\) 的最后一项 \(a_n\)，可见

• 若 \(a_n = a_{n-1}\)，则最好让 \(a_{n}\) 和 \(a_{n-1}\) 在同一段，这样 \(a_{n}\) 一定得分。
• 若 \(a_n \ne a_{n-1}\)，则最好把 \(a_{n}\) 和 \(a_{n-1}\) 分开，若不然 \(a_{n}\) 一定得分。

考虑 DP。定义 \(f[i]\) 为序列 \((A_1, \dots, A_i)\) 的最大得分。若 \(A_i = A_{i-1}\) 则 \(f[i] = f[i - 1] + A_i\)。若 \(A_i \ne A_{i-1}\)，考虑两种情况

• 不管 \(A_i\) 得不得分。归结为求 \(f[i - 1]\)。
• 让 \(A_i\) 得分。归结为选一项 \(A_j\) 满足 \(j < i - 1\) 且 \(A_j = A_i\)，把 \(A_{j+1}, \dots, A_{i-1}\) 分在一段。

对于第二种情况，若有多个满足条件的 \(j\)，取哪一个呢？应当最大的那个。

证明：把满足上述条件的最大的 \(j\) 记作 \(j'\)。注意到

• \(A_{j'}\) 和 \(A_{j'+1}\) 在不在同一段，只对 \(A_{j'+1}\) 是否得分有影响，对其他项是否得分没有影响。
• \(A_{j'}\) 是 \(A_i\) 左边第一个等于 \(A_i\) 的项，有 \(A_{j'} \ne A_{j'} + 1\)。若 \(A_{j'}\) 和 \(A_{j'+1}\) 在同一段，则 \(A_{j'+1}\) 一定不得分；若二者不在同一段，\(A_{j'+1}\) 有可能得分。

所以应当把 \(A_{j'}\) 和 \(A_{j'+1}\) 分开。

于是第二种情况进一步归结为计算下列两个东西

• \(f[j'+1]\)
• \(A_{j'+1}, \dots, A_{i-1}\) 那一段中，第二项到最后一项的总得分。

程序实现

/**
 *    author:  zjs
 *    created: 09.10.2026 14:47:05
**/
#include <bits/stdc++.h>
#include <cassert> // <bits/stdc++.h> does not include cassert since GCC 16.
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

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

    vector<int> last(1e6 + 5);
    vector<long long> f(n + 1);
    vector<long long> sum(n + 1);

    for (int i = 1; i <= n; i++) {
        if (a[i] == a[i - 1]) {
            f[i] = f[i - 1] + a[i];
        } else if (last[a[i]]) {
            int j = last[a[i]];
            f[i] = max(f[i - 1], f[j + 1] + sum[i - 1] - sum[j + 1] + a[i]);
        } else {
            f[i] = f[i - 1];
        }
        sum[i] = sum[i - 1] + (a[i] == a[i - 1]) * a[i];
        last[a[i]] = i;
    }
    cout << f[n] << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}