题解：CF811C Vladik and Memorable Trip

非常简单的 dp。

只需要暴力枚举每一个区间，然后判断合法后直接转移即可。

但是普通的判断合法会 TLE，需要预处理出每一个数在整个数组里的出现次数，然后把一个区间里的数全部插入到 set 中，遍历 set，如果在区间中出现次数等于整个数组中的出现次数，那么下次就不用判断，直接 erase，否则这个区间是不合法的。

另外注意没有区间可以转移时

dp_i \gets dp_{i-1}

。

CPP

signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i];
	for (int i=1;i<=n;i++) num[a[i]]++,ma=max(ma,a[i]);
	for (int i=1;i<=n;i++){
		for (int _=0;_<=ma;_++) cnt[_]=0;
		int sum=0;
		set<int> s;
		for (int j=i;j>=1;j--){
			bool f=1;
			if (!cnt[a[j]]) sum^=a[j],s.insert(a[j]);
			cnt[a[j]]++;
			vector<int> v;
			for (int x:s){
				if (cnt[x]!=num[x]){
					f=0;//不合法
					break;
				}
				else v.pb(x);
			}
			for (int x:v) s.erase(x);//下次不需要判断
			if (f) dp[i]=max(dp[j-1]+sum,dp[i]);//直接转移
		}
		dp[i]=max(dp[i],dp[i-1]);//没有区间可以转移
	}
	cout<<dp[n];
	return 0;
}

题解：CF811C Vladik and Memorable Trip

文章操作

相关推荐

评论

题解：CF811C Vladik and Memorable Trip