2024做题计划

难度范围：[绿-紫]

CSP-S2024 T3染色

首先动态规划显然，如何呢？不难设 \(f_{i}\) 表示对于前 \(i\) 个数来说的话，以 \(i\) 为结尾的答案的最大值，为啥是答案，因为这样可以直接转移 \(f_i=\max_{1\leq j<i}^{f_j+calc(j+1,i)+[a_j=a_i]\times a_i}\)
当然还有 \(f_i=\max{f_{i-1},f_i}\) 所以你就发现 \(f\) 有单调性，因为他可定大于等于上一个，然后你就发现答案就是 \(f_n\)。但是如果你直接转移是 \(O(n^2)\) 很显然会 TLE 。然后你发现如果有个 \(j\) 满足 \(a_j\) 不等于 \(a_i\) 那么会劣，那么又因为 \(f\) 单调，所以 \(f_i\) 从前一个与 \(a_i\) 的值相等的位置转移是不劣的，然后考虑开桶维护下上一次出现的位置就做完了！

代码：

#include<bits/stdc++.h>
using namespace std;
#define up(i,l,r) for(int i=l;i<=r;++i)
#define dn(i,l,r) for(int i=l;i>=r;--i)
#define int long long
const int N=2e5+5;
const int M=1e6+5;
int lst[M],a[N],n,f[N],pr[N],s[N];
inline void solve(){
	cin>>n;
	up(i,1,M-1) lst[i]=0;
	up(i,1,n){
		cin>>a[i];f[i]=0;s[i]=s[i-1]+(a[i]==a[i-1])*a[i];
		pr[i]=0;
	}
//	up(i,1,n) cout<<s[i]<<' ';
//	cout<<endl; 
	up(i,1,n){
		f[i]=f[i-1];pr[i]=lst[a[i]];
		if(lst[a[i]]){
			if(lst[a[i]]==i-1){
				f[i]=max(f[i],f[lst[a[i]]]+a[i]);
			}else{
				f[i]=max(f[i],f[lst[a[i]]+1]+a[i]+s[i]-s[lst[a[i]]+1]);
			}
		}
//		cout<<f[i]<<' ';
		lst[a[i]]=i;
	}
	cout<<f[n]<<'\n';
}
int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t;
	cin>>t;	
	while(t--) ::solve();
	return 0;
}
//tomxi