P8321 『JROI-4』沈阳大街 2 题解

先把期望成求和问题。

考虑一个非常厉害的转化：把两个序列 $a,b$ 拼接到一起得到序列 $c$，这样问题就变为了在序列 $c$ 上两两配对求所有最小价值的和。容易发现此时 $c$ 序列上顺序是无所谓的，因此对 $c$ 序列所有元素的值从大到小排序，此时一组配对对答案的贡献就是在序列上靠后的元素对答案的贡献。

考虑 dp。设 $f_{i,j}$ 表示当前匹配了 $c$ 序列的前 $i$ 个元素，当前已经匹配了 $j$ 对，所有合法匹配方案的价值的和。此时显然有初始条件 $f_{i,0}=1$，答案为 $f_{2n,n}$。

考虑转移。对于枚举的 $i,j$，现在要求出 $f_{i,j}$ 的值。那么有两种转移方法：

• 这个元素先留下来不匹配，和后面的某个元素匹配，此时转移方程为 $f_{i,j}\leftarrow f_{i-1,j}$。
• 这个元素和前面某个和其原来不在同一序列的元素匹配，此时可以枚举上一个匹配位置 $k$，转移方程形如 $f_{i,j}\leftarrow f_{i-1,j-1}\times c_i$。这个时候注意到转移式和 $k$ 没有关系，因此只需要计数 $i$ 前面和 $i$ 原来不在同一序列的元素的数量即可，这个可以一个前缀和求出来。

最后将答案乘以 $(n!)^{-1}$ 即可。总时间复杂度为 $O(n^2)$，可以通过该题。