这个题目如果动态规划数组是针对单点，最后会很难统计。因此设 \(dp_i\) 为 \(A\) 中前 \(i\) 个元素所能产生最大贡献。
有一个动态规划的思想就是，对于数列 \(A\) 中的每一个元素，我们可以选择要不要让他产生贡献。方便起见叫这个元素 \(x\)，他左边第一个和他值相等的元素叫 \(lst\)。
-
如果让他产生贡献，那么显然 \(x\) 和 \(lst\) 之间的所有格子都要涂成别的颜色。此时 $$dp_i = dp_{lst} + V(lst + 1, i - 1) + a_i$$其中 \(V(lst + 1, i - 1)\) 指把这一段全涂成一个颜色所能产生的贡献。
-
如果不产生贡献，那么 $$dp_i = dp_{i - 1}$$
考虑 \(V(lst + 1, i - 1)\) 如何计算。
我们发现，对于 \([lst + 2, i - 1]\) 的区间，可以确定在全涂一个颜色后它们会不会产生贡献。因为产不产生贡献只与左侧第一个与其同颜色的元素的数值有关。那么这些元素对 \(V\) 的贡献只需要判断一下左边第一个值是否一样就行。这个是可以预处理的。
rep(i, 1, n) {sum[i] = sum[i - 1];if(a[i] == a[i - 1]) {sum[i] += a[i]; //这样就可以后面O(1)计算}}
这样的话 \(V(a, b) = sum_b - sum_{a - 1}\)
而对于位置 \(lst + 1\) 则不能确定，因为在之前的最佳决策中，位置 \(lst + 1\) 左侧的第一个和他颜色一样的元素我们不知道值是多少。
因此咱们直接把 \(lst + 1\) 这个位置也扔到方程转移里，就像这样。
在实现的时候有个问题。 \(lst\) 可以等于 \(i - 1\)， 这样 \(sum_{i - 1} - sum_{lst + 1}\) 就是负数了。
那么我们可以把式子写做 $$dp_{lst + 1} + sum_{i} - sum_{lst + 1} + a_i$$
为什么合法呢？这样不会多算 \(i\) 位置的贡献吗？
答案是不会。分类讨论一下，如果 \(lst = i - 1\)，那么减出来值为 0。如果小于，那么 \(sum_{i - 1} = sum_i\)， 没任何问题。
完整的代码！
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i <= b; ++i)
using namespace std;
const int N = 1000005;
long long v, t, n, a[N], lst[N], sum[N], dp[N];
inline void solve() {cin >> n;rep(i, 1, n) dp[i] = sum[i] = 0; rep(i, 1, n) {cin >> a[i];lst[a[i]] = 0;}rep(i, 1, n) {sum[i] = sum[i - 1];if(a[i] == a[i - 1]) {sum[i] += a[i];}}rep(i, 1, n) {dp[i] = dp[i - 1];if(lst[a[i]]) dp[i] = max(dp[lst[a[i]] + 1] + sum[i] - sum[lst[a[i]] + 1] + a[i], dp[i - 1]);lst[a[i]] = i;}cout << dp[n] << '\n';
}
int main() {ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> t;while(t--) {solve();}return 0;
}