不难想到的是子序列划分模型。
$O(n^3)$ 的 DP：
$f[i][x][y]$ 表示对于前 $i$ 个位置，上一个染成红色的是 $x$，上一个染成蓝色的是 $y$，此时得分的最大可能值。
那么有转移（由于每次都读取上一行的数据，这里压掉第一维）：
$$f[x][i] = \max_{x = 0}^{i - 2}( f[x][i - 1] + [a[i] = a[i - 1]] \times a[i]) $$
$$ f[i][x] = \max_{x = 0}^{i - 2}( f[i - 1][x] + [a[i] = a[i - 1]] \times a[i]) $$
$$ f[i - 1][i] = \max_{x = 0}^{i - 2}( f[i - 1][x] + [a[i] = a[x]] \times a[i]) $$
$$ f[i][i - 1] = \max_{x = 0}^{i - 2}( f[x][i - 1] + ]a[i] = a[x]] \times a[i]) $$
发现它是 $O(n^2)$ 的，喜提 $50pts$。
由于我太菜了，不能直接从转移或者问题的性质中得出优化，所以考虑输出 $f[i][j]$ 找规律优化。
观察由大样例第一个数据得出的表（$18$ 为输出的答案）：
18
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 5 10 10 10 10 10 10
0 0 0 0 0 0 0 0 5 0 5 5 5 5 5 5
5 5 5 5 5 5 5 5 10 5 0 10 10 10 10 10
5 5 5 5 5 5 5 5 10 5 10 0 15 15 15 15
5 5 5 5 5 5 5 5 10 5 10 15 0 15 15 15
5 5 5 5 5 5 5 5 10 5 10 15 15 0 15 15
5 5 5 5 5 5 5 5 10 5 10 15 15 15 0 18
5 5 5 5 5 5 5 5 10 5 10 15 15 15 18 0
容易发现蓝色与红色是对称的，所以我们先想办法把一半优化掉。
考虑使 $f[i][j],i < j$。
我们再画个转移图：
考虑我们上面得到的 $f[i - 1][i]$ 的转移会跨越对角线，而又由对称性可知 $f[i - 1][x] = f[x][i - 1]$，所以这个转移可以被改成不跨越对角线的。
那么有：
$$f[x][i] = \max_{x = 0}^{i - 2}( f[x][i - 1] + [a[i] = a[i - 1]] \times a[i]) $$
$$ f[i - 1][i] = \max_{x = 0}^{i - 2}( f[x][i - 1] + [a[i] = a[x]] \times a[i]) $$
现在得出的表：
18
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 5 10 10 10 10 10 10
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 0 10 10 10 10 10
0 0 0 0 0 0 0 0 0 0 0 0 15 15 15 15
0 0 0 0 0 0 0 0 0 0 0 0 0 15 15 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 18
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
继续集中注意力，注意到除非 $a[i] = a[i - 1]$，否则答案好像总是在对角线旁边？（猜想）
继续注意。发现从上面的表中向右走等价于 $i$ 和 $i - 1$ 被染为同色。
注意到向右走的答案会更大当且仅当 $a[i] = a[i - 1]$。所以，猜想正确。
考虑不存在长度 $\ge 2$ 的相同 $a[i]$ 段的情况，对于所有 $i$，它的答案都在对角线旁边。
先处理不存在长度 $\ge 2$ 的相同 $a[i]$ 段的情况。考虑如何写出代码。
再观察一遍转移图：
显然，在没有长度 $\ge 2$ 相同段的情况下，有
$$f[i][j] = f[i][j + 1] \ (j > i)$$
而每一次 $f[i][i + 1]$ 的转移只与 $f[j][i] \ (0 \le j < i)$ 有关。
联立得，每一次 $f[i][i + 1]$ 的转移只与 $f[j][j + 1] \ (0 \le j < i)$ 有关。
此时如何优化已经显而易见。
用 $f[i]$ 表示上面的 $f[i][i + 1]$。
由之前得出的转移：
$$ f[i - 1][i] = \max_{x = 0}^{i - 2}( f[x][i - 1] + [a[i] = a[x]] \times a[i]) $$
则在上述情况下，
$$f[i - 1] = \max_{x = 0}^{i - 2} (f[x] + [a[i] = a[x]] \times a[i]) \ (1 \le i \le n)$$
阶段性成果：
#include <bits/extc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2020;
int n,a[MAXN];
ll f[MAXN];
void init() {
memset(f,0,sizeof f);
cin >> n;
for(int i = 1;i <= n;i++) cin >> a[i];
}
void solve() {
init();
for(int i = 1;i <= n;i++){
for(int x = 0;x <= i - 2;x++){
f[i - 1] = max(f[i - 1],f[x] + (a[i] == a[x]) * a[i]);
}
}
cout << *max_element(f,f + n) << '\n';
}
int main(){
int t;
cin >> t;
while(t--) solve();
}
再考虑存在长度 $\ge 2$ 的相同 $a[i]$ 段的情况。
回忆我们刚刚干了什么，发现我们事实上做了：
$$f[i] \leftarrow f[i][j] \ (i < j \le n) $$
考虑这样的段，发现如果 $a[i] = a[i - 1]$，则由上面打的 $f$ 表发现：
$$f[i][j + 1] \leftarrow f[i][j] + a[i] \ (i < j < n) $$
对应到我们现在定义的状态，则有
$$f[j] \leftarrow f[j] + a[i] \ (0 \le j < i - 1) $$
暴力加即可。
做完这些，我们得到了一个全新的，时间 $O(n^2)$，空间 $O(n)$ 的算法，仍然 $50pts$。
阶段性成果：
#include <bits/extc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 10;
int n,a[MAXN];
ll f[MAXN];
void init() {
cin >> n;
memset(f,0,sizeof(ll) * (n + 7));
for(int i = 1;i <= n;i++) cin >> a[i];
}
void solve() {
init();
for(int i = 1;i <= n;i++){
for(int x = 0;x <= i - 2;x++){
f[i - 1] = max(f[i - 1],f[x] + (a[i] == a[x]) * a[i]);
}
if(a[i] == a[i - 1]){
for(int j = 0;j <= i - 2;j++) f[j] += a[i];
}
}
cout << *max_element(f,f + n) << '\n';
}
int main(){
int t;
cin >> t;
while(t--) solve();
}
继续优化。
观察上述转移方程，分类讨论发现：
$$f[i - 1] = \max(\max_{1 \le j \le i - 2} f[j] ,\max_{1 \le j \le i - 2,a[j] = a[i]}f[j] + a[i])$$
因此考虑记录 $f[j]$ 的最大值和 $a[j] = C$ 的 $f[j]$ 最大值（开桶记录），直接转移即可。
做完这些，我们得到了一个全新的，时间 $O(n^2)$，空间 $O(n)$ 的算法，但是常数比上一个小一点，喜提 $60pts$。
阶段性成果：
#include <bits/extc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 10,MAXV = 1e6 + 10;
int n,a[MAXN];
ll f[MAXN],premax,maxlst[MAXV];
void init() {
cin >> n;
memset(f,0,sizeof(ll) * (n + 7));
premax = 0;
for(int i = 1;i <= n;i++) cin >> a[i],maxlst[a[i]] = 0;
}
void solve() {
init();
for(int i = 2;i <= n;i++){
f[i - 1] = max(premax,maxlst[a[i]] ? f[maxlst[a[i]]] + a[i] : 0);
if(a[i] == a[i - 1]) {
premax += a[i];
for(int j = 0;j <= i - 2;j++) {
f[j] += a[i];
}
}
premax = max(premax,f[i - 1]);
if(maxlst[a[i - 1]] == 0 || f[i - 1] > f[maxlst[a[i - 1]]]) maxlst[a[i - 1]] = i - 1;
}
cout << *max_element(f,f + n) << '\n';
}
int main(){
int t;
cin >> t;
while(t--) solve();
}
不难发现要实现前缀加，单点查，所以直接糊一个 BIT 上去就完事了！！！11。
时间复杂度 $O(n \log n)$，空间复杂度 $O(n + V)$。
注意 BIT 下标必须从 $1$ 开始，所以我们把所有下标 $ + 1$。
由于没有把修改直接应用于 $f$，所以输出答案时要输出 $premax$ 而不是 $\max f[i]$。
#include <bits/extc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 10,MAXV = 1e6 + 10;
int n,a[MAXN];
ll f[MAXN],premax,maxlst[MAXV],ans;
struct bit{
ll t[MAXN];
void init(){
memset(t,0,sizeof(ll) * (n + 7));
}
int lb(int x){
return x & -x;
}
void add(int loc,ll val){
for(int i = loc;i <= n;i += lb(i)) t[i] += val;
}
void add(int l,int r,ll val){
add(l,val),add(r + 1,-val);
}
ll query(int loc){
ll res = 0;
for(int i = loc;i;i -= lb(i)) res += t[i];
return res;
}
} t;
void init() {
cin >> n;
memset(f,0,sizeof(ll) * (n + 7));
t.init();
premax = ans = 0;
for(int i = 1;i <= n;i++) cin >> a[i],maxlst[a[i]] = 0;
}
void solve() {
init();
for(int i = 2;i <= n;i++){
f[i - 1] = max(premax,maxlst[a[i]] ? f[maxlst[a[i]]] + t.query(maxlst[a[i]] + 1) + a[i] : 0);
if(a[i] == a[i - 1]) {
premax += a[i];
t.add(1,i - 1,a[i]);
}
premax = max(premax,f[i - 1]);
if(maxlst[a[i - 1]] == 0 || f[i - 1] > f[maxlst[a[i - 1]]] + t.query(maxlst[a[i - 1]] + 1)) maxlst[a[i - 1]] = i - 1;
}
cout << premax << '\n';
}
int main(){
int t;
cin >> t;
while(t--) solve();
}
