题意理解

我们有一个长度为 $n$ 的正整数数组 $A$，要给每个数染成红色或蓝色。

对于每个位置 $i$：

• 如果 $A_i$ 左边没有同色的数，则 $C_i = 0$。
• 否则，设左边最近的同色数是 $A_j$：
  • 如果 $A_i = A_j$，则 $C_i = A_i$；
  • 否则 $C_i = 0$。

得分是 $\sum_{i=1}^n C_i$，我们要最大化这个得分。

关键观察

1. 得分来源
   只有当某个位置 $i$ 和它左边最近的同色位置 $j$ 的值相等时，才能得到 $A_i$ 的分数。
   也就是说，得分来源于相邻同色的相同数值对（相邻指的是在染色序列中相邻的同色位置，中间没有同色的数）。

2. 染色策略
   我们可以把数组分成若干段，每一段内部染成同一种颜色，并且相邻段颜色不同。
   这样，每一段内部的相邻相同数值对都可以贡献分数。

3. 问题转化
   假设我们有一个子数组 $[A_l, A_{l+1}, \dots, A_r]$ 染成同色，那么对于这个子数组：

   • 第一个位置 $l$ 没有左边同色数，所以 $C_l=0$。
   • 对于 $k = l+1$ 到 $r$，如果 $A_k = A_{k-1}$，则 $C_k = A_k$，否则 $C_k=0$。

   所以这一段的总得分就是 $\sum_{k=l+1}^r [A_k = A_{k-1}] \cdot A_k$。

4. 分段与颜色交替
   我们可以把整个数组分成若干段，每段同色，相邻段异色。
   得分就是所有段内部相邻相等数值的 $A_k$ 之和。

5. 最优分段
   问题变成：在数组上切若干刀，把数组分成若干段，最大化所有段内部的相邻相等数值的 $A_k$ 之和。
   注意：段长度至少为 1。

6. 动态规划
   设 $dp[i]$ 表示考虑前 $i$ 个元素的最大得分。
   转移：

   • 要么 $i$ 单独成一段：$dp[i] = dp[i-1]$。
   • 要么 $i$ 和前面若干元素成一段：如果 $A_i = A_{i-1}$，则从 $dp[i-2]$ 转移过来并加上 $A_i$；更一般地，如果从 $j+1$ 到 $i$ 成一段，那么这段的得分是 $\sum_{t=j+2}^i [A_t = A_{t-1}] \cdot A_t$。
     但这样直接做是 $O(n^2)$ 的，不可行。

最终算法

1. 初始化两个数组 $lastR$ 和 $lastB$（字典或数组，因为 $A_i \le 10^6$，可以开数组大小 $10^6+1$），表示当前以红色/蓝色结尾，且末尾值是 $v$ 时的最大得分。
2. 初始化 $best = 0$。
3. 遍历 $i=1$ 到 $n$：
   • 计算新状态：
     • 如果 $A_i$ 染红色：
       • 从 $lastB$ 中所有值中取最大值 $mb$（即上一个颜色是蓝色的最大得分），作为不配对的情况。
       • 如果 $lastR[A_i]$ 存在，则配对得分 = $lastR[A_i] + A_i$。
       • 新红色得分 = $\max(mb, lastR[A_i] + A_i)$。
     • 同理处理蓝色。
   • 更新 $lastR[A_i]$ 和 $lastB[A_i]$。
   • 更新 $best$。
4. 输出 $best$。

这样复杂度 $O(n)$，空间 $O(\max A_i)$。

算法标签

• 动态规划
• 贪心优化
• 状态压缩

样例验证

样例1：1 2 1
最优：1（红），2（蓝），1（红）
得分：第三个1和第一个1同色且中间无红，相等，得1。
输出1，符合。

样例2：1 2 3 4
无相等对，输出0。

样例3：3 5 2 5 1 2 1 4
输出8，符合。

最终题解：

我们通过动态规划，维护以某种颜色结尾且末尾为某数值时的最大得分，实现 $O(n)$ 的解法。

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

const int MAX_A = 1e6 + 5;

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

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

        vector<int> lastR(MAX_A, -1), lastB(MAX_A, -1);
        int bestR = 0, bestB = 0;

        for (int i = 0; i < n; i++) {
            int v = A[i];
            int newR = max(bestB, (lastR[v] != -1 ? lastR[v] + v : bestB));
            int newB = max(bestR, (lastB[v] != -1 ? lastB[v] + v : bestR));

            lastR[v] = max(lastR[v], newB);
            lastB[v] = max(lastB[v], newR);

            bestR = max(bestR, newR);
            bestB = max(bestB, newB);
        }

        cout << max(bestR, bestB) << "\n";
    }

    return 0;
}