题解

思路

一个偶数长度区间能够被完全删除，当且仅当其中任意数的出现次数都不超过区间长度的一半。必要性显然；充分性可以不断在不同数的相邻块边界删除一对，并保持最大频次不超过剩余长度的一半。

固定最终保留的值。若保留位置 $j<i$，它们之间的全部元素必须能够完全删除；第一个保留位置之前与最后一个保留位置之后也必须能够完全删除。因此问题转化为在相同值的位置之间做最长链动态规划。

做法

极小层直接广度优先搜索所有可达数组状态。

中档层枚举每个区间，并重新扫描区间统计最大频次，以 $O(n^3)$ 时间得到全部可删区间。

满分层固定左端点向右扩展，用频次数组增量维护最大频次，在 $O(n^2)$ 时间得到可删表。令 $dp_i$ 为前缀处理到位置 $i$ 且保留 $a_i$ 时的最大保留数：若前缀 $[1,i-1]$ 可删，则 $dp_i$ 至少为 1；若 $j<i$、$a_j=a_i$ 且区间 $(j,i)$ 可删，则可由 $dp_j+1$ 转移。最后只接受后缀可删的位置。

复杂度

满分做法每个测试用例时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。