CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!) C. Tenzing and Balls

一开始以为是贪心，后来发现不好贪于是选择了dp，但是dp有个小细节没注意到，后面wa了几发

我们以状态来分,f[i]表示考虑i的最大区间合长度，每次转移的时候考虑两种情况，一种是a[i]前面有一样的数字，比较选了a[i]和不选a[i]两种情况下的最大值，还有一种就是a[i]为第一个出现的数字则选区间长度不变

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
const int N=2e5+10;
int f[N],last[N];//last记录上一次该数字出现的位置
int n,t;
void solve(){
	cin>>n;
	int res=0;
	memset(last,-1,sizeof last);
	memset(f,0,sizeof f);
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		f[i]=max(f[i],f[i-1]);
		if(last[x]!=-1) {
		int k;
        //这里是处理细节，考虑到就是a[last[x]]有没有对f[last[x]]作出贡献，如果有就需要去除该元素
		if(f[last[x]]!=f[last[x]-1]) k=f[last[x]]+i-last[x];
		else k=f[last[x]]+i-last[x]+1;
		f[i]=max(f[i],k);
	}
		res=max(res,f[i]);
		last[x]=i;//更新上次出现的位置
}
	cout<<res<<endl;
	
}
int main(){
	cin>>t;
	while(t--){
		solve();
	}
}