eclipse 题解

Statement

给定一个圆，圆按照顺时针排布着 \(2n\) 个点，依次编号为 \(1\sim n\)，其中编号为 \(1\sim n\) 的点属于 Alice，编号为 \((n+1)\sim 2n\) 的点属于 Bob。

同时给出两个长度为 \(n\) 的序列 \(A,B\)。

你需要确定一个最大的正整数 \(K\)，使得存在 \(K\) 个二元组 \((x_i,y_i)\) 满足 \(1\leq x_i\leq n < y_i\leq 2n, A_{x_i} = B_{y_i-n}\)，且任意两个二元组在圆上对应的连线在圆内不交（也不能交于 \(2n\) 个点中的任意一个），同时构造出对应的 \(\{x_i\}\)。

\(1\leq n\leq 5000\)。

Solution

考虑将 \(\{B\}\) 翻转，此时问题变成找出两个长度为 \(K\) 且升序的序列 \(\{P\},\{Q\}\)，且 \(\forall i\in [1,K], A_{P_i} = B_{Q_i}\)。

翻转之后等价于当按照 \(P\) 升序考虑的时候，\(Q\) 没有逆序对。

考虑 DP，记 \(f_{i,j}\) 表示考虑到 \(A\) 的前 \(i\) 个，\(B\) 已经匹配到第 \(j\) 个，同时记 \(nxt_{i,j}\) 表示位置 \(i\) 以后第一个与 \(a_j\) 相同的 \(b_k\) 的 \(k\) 的值，没有则为 \(n+1\)。

若选择不匹配 \(A_i\)，则 \(f_{i,j}\to f_{i+1,j}\)，若选择匹配 \(A_i\)，则 \(f_{i,j}+1 \to f_{i+1,nxt_{j,i}}\)。

输出方案则考虑记录 DP 路径即可。