【题解】AGC030F Permutation and Minimum

2023-12-26 16:30:33

去掉所有的 \((a_i,a_j)\)，剩下了一堆 \((a_i,-)\) 和 \((-,-)\) 。因为 \((-,-)\) 是等价的，方案数大概很容易推，这点我们等下再说。

接着就是一堆 \((a_i,-)\) 怎么计算方案数，放在一起 dp，设 \(f_{i,j,k}\) 表示从后往前第 \(i\) 个，有 \(j\) 个普通失配点和 \(k\) 个限制失配点，考虑当前数是否作为一对数的最小值，或者不选即可。