题解：AT_abc381_f [ABC381F] 1122 Subsequence

cppcppcpp3 · 2024-11-23 13:28:50 · 题解

题意

定义一个正整数序列 \{b_1,b_2,\cdots,b_m\} 为 1122 数列 当且仅当序列满足以下所有条件：

1. m\equiv 0\pmod 2
2. 对于所有 1\le i\le \frac{m}{2} 的整数 i，满足 b_{2i-1}=b_{2i}。
3. 在 b 中出现过的整数恰好出现 2 次。

给出长度为 n 的序列 a，求出 a 的（可以不连续）子序列中，是 1122 数列 的序列的长度最大值。

思路

比较简单的状压 dp，还好场切了。

假设我们现在尝试构造一个合法序列。称 a_i 的值为颜色，用一次颜色 x 表示将两个满足 a_i=x 的不同下标加入序列末尾。由条件 3 每种颜色至多会被使用一次。同时我们每次往序列末尾添加某个颜色，只关注用过的最大下标（即加入颜色前序列末尾的下标），以及哪些颜色已经被用过，而由于颜色数 m\le 20，把这个信息记录下来是可行的。

考虑大概按照这个每次向序列末尾添加一个颜色的过程 dp，把我们关注的两样东西记入状态：记 f(i,S)=0/1 表示顺次考虑到末尾下标为 i 的序列，使用颜色的集合为 S 是否可行（注意到序列长度即 2|S|，不用记录什么“最大长度”）。转移枚举一个没用过的颜色 x 加到末尾，贪心地选取 i 之后最近的两个下标 j,k 且 j<k,a_j=a_k=x，转移到 f(k,S\cup\{x\})。状态数 O(n2^m)。

考虑优化状态。实际上你往一个前面已经决定好的序列末尾加入一个颜色，只关心的是颜色的集合，这些用过的颜色怎么排列是不重要的。而且 bool 的状态太浪费了，完全可以把 i 扔进状态对应的值里面去，即对同样颜色集合构成的序列只取末尾最靠前的转移。此时状态变为 f_S，表示使用颜色集合为 S 的合法序列，序列末尾下标的最小值。转移类似枚举 x，取最前的两个下标 j,k 满足 f_S<j<k,a_j=a_k=x，更新 f_{S\cup \{x\}} \to \min(f_{S\cup \{x\}},k)。

最终 ans=\max\limits_{f_S\le n}|S|，时间复杂度 O(m2^m\log n)，对数来自二分求 j,k。

My Submission