参考了这篇题解，以及机房大佬的讲解
题目描述
给定一个长度为 \(n\) 的正整数数组 \(A\)，其中所有数从左至右排成一排。
你需要将 \(A\) 中的每个数染成红色或蓝色之一，然后按如下方式计算最终得分：
设 \(C\) 为长度为 \(n\) 的整数数组，对于 \(A\) 中的每个数 \(A_i\)（\(1 \leq i \leq n\)）：
- 如果 \(A_i\) 左侧没有与其同色的数，则令 \(C_i = 0\)。
- 否则，记其左侧与其最靠近的同色数为 \(A_j\)，若 \(A_i = A_j\)，则令 \(C_i = A_i\)，否则令 \(C_i = 0\)。
你的最终得分为 \(C\) 中所有整数的和，即 \(\sum \limits_{i=1}^n C_i\)。你需要最大化最终得分，请求出最终得分的最大值。
输入格式
本题有多组测试数据。
输入的第一行包含一个正整数 \(T\)，表示数据组数。
接下来包含 \(T\) 组数据，每组数据的格式如下：
第一行包含一个正整数 \(n\)，表示数组长度。
第二行包含 \(n\) 个正整数 \(A_1, A_2, \dots, A_n\)，表示数组 \(A\) 中的元素。
输出格式
对于每组数据：输出一行包含一个非负整数，表示最终得分的最大可能值。
输入输出样例 #1
输入 #1
3
3
1 2 1
4
1 2 3 4
8
3 5 2 5 1 2 1 4
输出 #1
1
0
8
说明/提示
【样例 1 解释】
对于第一组数据，以下为三种可能的染色方案：
- 将 \(A_1, A_2\) 染成红色，将 \(A_3\) 染成蓝色（\(\red{1}\red{2}\blue{1}\)），其得分计算方式如下：
- 对于 \(A_1\)，由于其左侧没有红色的数，所以 \(C_1 = 0\)。
- 对于 \(A_2\)，其左侧与其最靠近的红色数为 \(A_1\)。由于 \(A_1 \neq A_2\)，所以 \(C_2 = 0\)。
- 对于 \(A_3\)，由于其左侧没有蓝色的数，所以 \(C_3 = 0\)。
该方案最终得分为 \(C_1 + C_2 + C_3 = 0\)。
- 将 \(A_1, A_2, A_3\) 全部染成红色（\(\red{121}\)），其得分计算方式如下：
- 对于 \(A_1\)，由于其左侧没有红色的数，所以 \(C_1 = 0\)。
- 对于 \(A_2\)，其左侧与其最靠近的红色数为 \(A_1\)。由于 \(A_1 \neq A_2\)，所以 \(C_2 = 0\)。
- 对于 \(A_3\)，其左侧与其最靠近的红色数为 \(A_2\)。由于 \(A_2 \neq A_3\)，所以 \(C_3 = 0\)。
该方案最终得分为 \(C_1 + C_2 + C_3 = 0\)。
- 将 \(A_1, A_3\) 染成红色，将 \(A_2\) 染成蓝色（\(\red{1}\blue{2}\red{1}\)），其得分计算方式如下：
- 对于 \(A_1\)，由于其左侧没有红色的数，所以 \(C_1 = 0\)。
- 对于 \(A_2\)，由于其左侧没有蓝色的数，所以 \(C_2 = 0\)。
- 对于 \(A_3\)，其左侧与其最靠近的红色数为 \(A_1\)。由于 \(A_1 = A_3\)，所以 \(C_3 = A_3 = 1\)。
该方案最终得分为 \(C_1 + C_2 + C_3 = 1\)。
可以证明，没有染色方案使得最终得分大于 \(1\)。
对于第二组数据，可以证明，任何染色方案的最终得分都是 \(0\)。
对于第三组数据，一种最优的染色方案为将 \(A_1, A_2, A_4, A_5, A_7\) 染为红色，将 \(A_3, A_6, A_8\) 染为蓝色（\(\red{35}\blue{2}\red{51}\blue{2}\red{1}\blue{4}\)），其对应 \(C = [0, 0, 0, 5, 0, 2, 1, 0]\)，最终得分为 \(8\)。
【样例 2】
见选手目录下的 color/color2.in 与 color/color2.ans。
【数据范围】
对于所有测试数据，保证：\(1\leq T\leq 10\)，\(2\leq n\leq 2\times 10^5\)，\(1\leq A_i\leq 10^6\)。
::cute-table{tuack}
| 测试点 | \(n\) | \(A_i\) |
|---|---|---|
| \(1\sim 4\) | \(\leq 15\) | \(\leq 15\) |
| \(5\sim 7\) | \(\leq 10^2\) | \(\leq 10^2\) |
| \(8\sim 10\) | \(\leq 2000\) | \(\leq 2000\) |
| \(11,12\) | \(\leq 2\times 10^4\) | \(\leq 10^6\) |
| \(13\sim 15\) | \(\leq 2\times 10^5\) | \(\leq 10\) |
| \(16\sim 20\) | ^ | \(\leq 10^6\) |
思路
可以先用\(lst_{a_i}\)表示在\(a_i\)前面最近的与\(a_i\)的值一样的数的位置，那么dp转移时就可以考虑\(a_i\)要或不要和\(lst_{a_i}\)染成一样的颜色
如果\(lst_{a_i}\)和\(a_i\)的颜色一样，那么他们之间的所有值的颜色必须一样
所以对于上图的蓝色部分，颜色都一样（颜色相同的左边最近的数就是相邻的），所以要看每个相邻的两数的贡献，所以我们可以用一个\(s\)数组前缀和的预处理出相邻两数的贡献，然后如果需要哪个区间只需\(s_r-s_{l-1}\)即可
预处理部分
for(int i=2;i<=n;i++){if(a[i]==a[i-1]){s[i]=s[i-1]+a[i];}else{s[i]=s[i-1];}
}
如果不和前面前面染成一样的颜色，那么
如果染成一样的颜色，那么
所以，我们讲如图的橙色部分的贡献相加即可通过
一些问题
Q:为什么是\(dp_{lst_{a_i}+1}\)?
A:
如果像这样，\(dp_{lst_{a_i}+1}\)的前面也有和\(dp_{lst_{a_i}+1}\)一样颜色的点怎么办？
用\(dp_{lst_{a_i}}\)会漏算
用\(dp_{lst_{a_i}+2}\)或这更后面的会重复计算，因为只能最近的
AC代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
const int maxn=1e6+5;
int a[N],s[N];
int dp[N];
int lst[maxn];
signed main(){int t;cin>>t;while(t--){int n;cin>>n;for(int i=1;i<=1e6;i++){lst[i]=0;}for(int i=1;i<=n;i++){cin>>a[i];dp[i]=0;s[i]=0;}for(int i=2;i<=n;i++){if(a[i]==a[i-1]){s[i]=s[i-1]+a[i];}else{s[i]=s[i-1];}}for(int i=1;i<=n;i++){dp[i]=dp[i-1];if(lst[a[i]]){dp[i]=max(dp[i],dp[lst[a[i]]+1]+a[i]+s[i-1]-s[lst[a[i]]]);}lst[a[i]]=i;//更新最近的位置}cout<<dp[n]<<endl;} return 0;
}