AcWing 每日一題 3697. 回文子序列

原題連結

資料範圍

1≤T≤100,

3≤n≤5000,

1≤ai≤n,

一個測試點内所有 n 的和不超過 5000。

輸入樣例：

5

3

1 2 1

5

1 2 2 3 2

3

1 1 2

4

1 2 2 1

10

1 1 2 2 3 3 4 4 5 5

輸出樣例：

YES

YES

NO

YES

NO

注意，這裡是回文子序列，隻需要有兩個相等的數不相鄰即可，然後中間随便選一個數，就能構成回文子序列

AC代碼：

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int maxn=5003;
int a[maxn];
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n;	
		bool flag=0;
		scanf("%d",&n);
		memset(a,0,sizeof(a));
		int pre=0;
		for(int i=1;i<=n;++i){
			int x;
			scanf("%d",&x);
			if(!a[x])a[x]=i;
			if(a[x]&&i-a[x]>1)flag=1;
		}
		if(flag)printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}