abc397c

思路：

本题其实还是挺套路的。

首先，因为题目要求我们把原数组分成两段，求两段数组不重复的数的和的最大值。看一下数据范围，

n \le 3 \times 10^5

，所以我们要用类似前缀和预处理的方式。

首先，从前往后预处理。当出现新元素时，就把预处理数组比之前加

1

。否则直接复制前一个元素。从后往前同理。

算答案时，把两段和的最大值求一下就行了。

代码：

CPP

#include<bits/stdc++.h>
//#define int long long
using namespace std;
int s1[300005],s2[300005],n,a[300005];
map<int,bool>m1,m2;
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=1;i<=n;++i){
		if(!m1[a[i]]){
			s1[i]+=s1[i-1]+1;
			m1[a[i]]=1;
		}
		else s1[i]+=s1[i-1];
	}
	for(int i=n;i>=1;--i){
		if(!m2[a[i]]){
			s2[i]+=s2[i+1]+1;
			m2[a[i]]=1;
		}
		else s2[i]+=s2[i+1];
	}
//	for(int i=1;i<=n;++i) cout<<s1[i]<<' '<<s2[i]<<'\n';
	int ans=0;
	for(int i=1;i<n;++i)
		ans=max(ans,s1[i]+s2[i+1]);
	cout<<ans;
	return 0;
}

文章操作

思路：

代码：

相关推荐

评论

abc397c