暴力DFS+记忆化

2
15
5 3 7 2 4 13 11 6 5 5 3 5 12 8 13
15
1 12 11 11 7 11 15 6 4 6 3 15 7 5 2

#include <bits/stdc++.h>
using namespace std;
#define N 350005
#define Red 2
#define Blue 1

int a[N];
int record[N];
int n;
int ans = 0;
void dfs(int u, int blue, int red, int sum, int Color) {
	
	if (u > n) {
		
		ans = max(ans, sum);
		return;
	}

	

	if (record[u] == -1) {
		record[u] = sum;
	} else {
		if(record[u]>sum)return;
		else record[u]=sum;
	}

	
	
	if(Color==Blue){
		if(a[blue]==a[u])sum+=a[u];
		dfs(u+1,u,red,sum,Blue);
		dfs(u+1,u,red,sum,Red);
	}
	if(Color==Red){
		if(a[red]==a[u])sum+=a[u];
		dfs(u+1,blue,u,sum,Red);
		dfs(u+1,blue,u,sum,Blue);
	}
	
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie();
	cout.tie();
	int T;
	cin >> T;
	while (T--) {
		ans=0;
		cin >> n;
		
		for (int i = 1; i <= n + 2; i++)record[i] = -1;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}
		
		dfs(1,0,0,0,Blue);
		dfs(1,0,0,0,Red);
		cout<<ans<<endl;
		
		
	}
	//freopen("detect3.in","r",stdin);
	//freopen("detect.out","w",stdout);
	
	
	
	return 0;
}