自动搬运

查看原文

来自洛谷，原作者为

	yummy 这个人是时代的眼泪，什么也没有留下

搬运于2025-08-24 23:05:04，当前版本为作者最后更新于2024-10-13 13:23:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

D. 配对序列 (pairing) 官方题解

本题考查的主要知识点有：

• 【4】简单一维动态规划

送分

读题后不难发现测试点 $10$ 的输出为 $0$。

对于测试点 $11$，一个数可以出现在答案中当且仅当该数字出现了 $2$ 次。所以统计出现至少两次的数字种数再乘以 $2$ 即可。

前 $2$ 个测试点可以直接枚举子序列，然后判断是否符合题意，时间复杂度 $O(n2^n)$。

如果考场上没有任何思路，那么这 $20$ 分可以尝试拿到手。

朴素的 DP

题目也是让你求某种子序列的个数，类似求最长上升子序列，我们考虑 DP。

令 $f(i)$ 为以 $i$ 结尾的最长配对子序列的长度，则每次转移要枚举 $i$ 的上一个数的位置 $j$ 和上上个数的位置 $k$，如果 $a_i=a_j$ 且 $a_j\ne a_k$，那么 $f_i$ 可以变成 $\max(f_i, f_k+2)$。该方法时间复杂度为 $O(n^3)$，可以通过测试点 $1\sim 5$ 拿到 $25$ 分，如果结合送分，可得 $35$ 分。

我们发现时间复杂度瓶颈在于每次转移需要枚举两个数。如果我们能把长度为奇数的子序列也写进某种 DP 里，那么每次转移只要枚举上一个数的位置。

令 $even(i)$ 表示以 $i$ 结尾的最长配对子序列长度，$odd(i)$ 表示以 $i$ 结尾，除了长度是奇数以外都满足配对子序列的要求的、最长子序列长度。

转移 $even(i)$ 时，枚举所有 $j<i$，如果 $a_j=a_i$，那么用 $odd(j)+1$ 去更新 $even(i)$。

转移 $odd(i)$ 时，枚举所有 $j<i$，如果 $a_j\ne a_i$，那么用 $even(j)+1$ 去更新 $odd(i)$。

时间复杂度 $O(n^2)$，可得 $45$ 分，结合送分可得 $55$ 分。

更优秀的 DP

经过观察，发现如果 $a_i=a_j$，且 $i<j$，那么 $j$ 处的 DP 值一定大于 $i$ 处的 DP 值（因为 $j$ 的转移范围大于 $i$ 的转移范围）。因此转移 $even(i)$ 时，我们只需要找到 $i$ 之前最近的和 $a_i$ 相等的 $a_j$ 进行转移。实现上，在 $i$ 从前往后扫描的过程中，用 $pre_v$ 来记录 $a$ 中上一次出现数 $v$ 的位置即可。

对于 $odd(i)$，如果是测试点 $12\sim 14$，那么只需要在 $i$ 从前往后循环的同时记录下 $even(i)$ 的最大值即可——毕竟因为所有数最多出现 $2$ 次，如果 $a_ i$ 是第一次出现，那么 $i$ 之前的 $j$ 都有 $a_j\ne a_i$；而如果 $a_i$ 是第二次出现，这个 $odd(i)$ 就不可能再被某种 $even(j)$ 调用，正确性也就不重要了。

然而对于所有测试点，只记录 $even(i)$ 最大值（记为 $even(J)$）是不够的——如果 $a_i=a_J$，那么这时就要转而求“次大值”。总而言之，我们需要在 $i$ 从前往后循环的同时，记录 $a_J$ 不同的 $even(J)$ 前二大。

这样，总时间复杂度就是 $O(n+\max a_i)$ 的了，可以通过。

#include<bits/stdc++.h>
using namespace std;
const int N=500005;
int n,a[N],even[N],odd[N],pre[N];
int main(){
	scanf("%d",&n);
	int b1=0,b2=0;
	odd[0]=-1e9;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[b1]==a[i])
			odd[i]=even[b2]+1;
		else odd[i]=even[b1]+1;
		even[i]=odd[pre[a[i]]]+1;
		if(even[i]>=even[b1]){
			if(a[i]!=a[b1])
				b2=b1;
			b1=i;
		}
		else if(even[i]>=even[b2] && a[i]!=a[b1])
			b2=i;
		pre[a[i]]=i;
	}
	printf("%d\n",even[b1]);
	return 0;
}