自动搬运

查看原文

来自洛谷，原作者为

	PassName AFO||他们到达过的终点，我也一定可以抵达

搬运于2025-08-24 23:05:33，当前版本为作者最后更新于2024-10-28 15:11:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

PS：声明，本做法由同机房巨佬

提供一个代码实现非常简单十分简短的做法。

返璞归真，状态没必要设置那么复杂，设 $f_i$ 表示考虑到第 $i$ 位的答案。显然的，对于每一个位置 $i$ 可以令 $f_i = f_{i-1}$。

用 $lst_i$ 记录 $i$ 上一次出现的位置，初始化令所有的 $lst_i = 0$，每遍历到一个位置，动态更新 $lst_{a_i} = i$。然后枚举区间更新 $f_i$，也可以预处理出来一个 $g$ 数组辅助转移，复杂度 $O(n^2)$。

50pts code

使用前缀和优化，每当 $a_i=a_{i-1}$ 时，更新前缀和数组 $s_i$。最后对于 $a_i$ 如果 $lst_{a_i}$ 存在，对于 $f_i$ 的转移为：

$$f_i=\max_{i=1}^{n}\{f_{lst_{a_i}+1}+a_i+s_i-s_{lst_{a_i}}\} $$

最终的答案为 $f_n$。

复杂度 $O(n)$。

#include <bits/stdc++.h>

#define int long long
#define rint register int
#define endl '\n'
#define m(a) memset(a, 0, sizeof a)

using namespace std;

const int N = 1e6 + 5;

int n, T;
int a[N], lst[N], f[N];
int s[N], ans; 

signed main() 
{
	cin >> T;
	while (T--) 
	{
		cin >> n;
		m(a), m(lst), m(f), m(s);
		for (rint i = 1; i <= n; i++) cin >> a[i];
		for (rint i = 2; i <= n; i++) s[i] = (a[i] == a[i - 1] ? s[i - 1] + a[i] : s[i - 1]);
		for (rint i = 1; i <= n; i++) 
		{
			f[i] = f[i - 1];
			if (lst[a[i]]) f[i] = max(f[i], f[lst[a[i]] + 1] + a[i] + s[i] - s[lst[a[i]] + 1]);
			lst[a[i]] = i;
		}
		cout << f[n] << endl;
	} 
	return 0;
}