最长回文子序列

题目背景
给你一个长度为 \(N\) 的序列 \(A\)，满足每个数字最多出现 \(K\) 次，求最长回文子序列的长度。

“最长回文子序列”说明：

子序列：对于一个序列 \(a=a_1,a_2,...,a_n\)，则非空序列 $ a′=a_{p_1},a_{p_2}\cdots,a{p_m} $为 \(a\) 的一个子序列，其中 \(1\le p_1\le p_2...\le p_m\le n\)。

例：\(1,3,4\) 是 \(1,2,3,4,5\) 的一个子序列。

回文序列：对于一个序列\(a=a_1,a_2,\cdots,a_n\)，对于任意 \(i(1\le i\le n)\)都满足 \(a_i=a_{n?i+1}\)。

例：\(1,2,7,2,1\) 和 \(6,5,5,6\) 都是回文序列。

最长回文子序列要求满足是原序列的子序列，且是回文序列的条件下，使得该序列最长。

例：\(1,2,7,2,1\) 是 \(1,3,2,7,4,2,1\) 的一个最长回文子序列。

输入格式
数据采用多组数据测试：

第一行包含一个正整数 \(T\)，表示数据的组数。

对于每一组数据输入描述如下：

第一行包括两个正整数 \(N,K\)。

第二行包括用空格隔开的 \(N\) 个正整数，描述整个数列。

输出格式
对于每组数据，每行一个整数，表示最长回文子序列的长度。

样例
input

3
4 3
1 1 2 1
8 2
1 3 4 2 1 2 3 4
10 4
3 2 3 8 1 8 2 8 3 3

output

3
5
7

样例解释
1.最长子序列为\(1,1,1\)或者\(1,2,1\)。

2.最长子序列为$3,2,1,2,3 $或者 \(4,2,1,2,4\)。

3.一种可能的最长子序列为\(3,2,8,1,8,2,3\)，其他情况略。

数据范围
时间限制：\(1s\)

空间限制：\(256M\)

对于所有数据，满足 \(T\le3,1\le A_i\le 10^5\)。

对于 \(N,K\) 数据范围如下：

先看一下怎么骗分。\(k=1\)时，答案一定是1.
\(n \le 10^3\)时，可以用区间DP骗40分。
定义\(dp_{i,j}\)为由i到j的最长回文子序列。，则\(dp_{i,j}=\max(dp_{i+1,j},dp_{i,j-1})\)
如果\(a_i=a_j,dp_{i,j}=dp_{i+1,j-1}+2\).
初始化\(dp_{i,i}=1\)
复杂度\(O(N^2)\)

我们再看一下k=2时的数据点。我们可以将相等的数作为一个数对.回文子序列一定是由外面一对又一对相同的数围出来的出来的。\(l_i\)为第i个数对的左端点，\(r_i\)为第i个数对的右端点定义\(dp_{i}\)为以第i对数为最外围的回文子序列。那么什么时候一对数可以从另一对数转移过来呢？\(l_i且\(r_j时，第i对数可以套住第j对数，\(dp_i\)可能为\(dp_j+2\)
复杂度还是\(O(N^2)\)
观察什么时候可以转移。我们将所有\(l_i\)从大到小排序后，\(dp_i\)可以从所有\(r_j\)小于\(r_i\)的转移。我们每求出一个dp值，就把他存在树状数组里面，然后每次的\(dp_i\)就是所有树状数组中\(r_j的\(dp_j\)的最大值，然后更新就可以了。复杂度\(O(NlogN)\)
那么k不等于2的时候呢？我们可以将k个相同的数两两为一个数对，排序后就跟k=2时一样了。复杂度\(O(NK^2log(nk^2))\).想一想怎么排序，肯定先按照左端点排序，但是对于一样的l时我们要按照r从大到小排序，避免同左端点的数对互相转移

#include
#include
#include
#include
using namespace std;
const  int N=5e4+5,M=1e5+5,T=4e6+5;
int s[M],g[M][5],idx,n,k,t,a[N],l,m,dp[N],ans,tr[N],ret;
struct node{
	int l,r;
	bool operator<(const node&n)const{
		if(l!=n.l)
			return l>n.l;
		return r>n.r;
	}
}hw[T];
void update(int x,int y)
{
	for(;x<=n;x+=x&-x)
		tr[x]=max(tr[x],y);
}
int ask(int x)
{
	ret=0;
	for(;x;x-=x&-x)
		ret=max(ret,tr[x]);
	return ret;
}
int main()
{
	scanf("%d",&t);
	while(t--) 
	{
		ans=1,m=0;
		memset(s,0,sizeof(s));
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",a+i);
			g[a[i]][++s[a[i]]]=i,tr[i]=1;
		}
		for(int i=1;i<=100000;i++)
			for(int j=1;j<=s[i];j++)
				for(int p=j+1;p<=s[i];p++)
					hw[++m]=(node){g[i][j],g[i][p]};
		sort(hw+1,hw+m+1);
		for(int i=1;i<=m;i++)
		{
			dp[i]=ask(hw[i].r-1)+2;
			update(hw[i].r,dp[i]);
			ans=max(ans,dp[i]);
		}
		printf("%d\n",ans);
	}
	return 0;
}