ABC238F Two Exams

题意

在一个地方有 $NN$ 名考生，共参加了两次考试两次考试的排名分别为 $P_i{Q}_{i}P\_i\; \backslash \; Q\_i$ 。现在要求选出 $KK$ 名考生，使得这 $KK$ 名考生中不存在某位考生的两次排名 $(P_i,Q_i)(P\_i\; ,\; Q\_i)$ 都比某位未选上的考生的两次排名$(P_j,Q_j)(P\_j,Q\_j)$ 低。

思路

对于该题目我们不妨将这些排名按照第一关键字为 $P_{i}P\_i$ 第二关键字为 $Q_{i}Q\_i$ 排序。

我们发现如果在后面的考生想要参选，那么依照我们的排序规则我们已经知道了 那么必须满足当前同学的排序 $Q_i>Q_{j}Q\_i\; >\; Q\_j$ 才可以参选。

由于 $P_{i}P\_i$ 顺序是固定的，那么我们不妨确定最小未选择 $Q_{i}Q\_i$ 作为我们的转移条件。

那么我们的方程就变成 $F[i][j][k]F[i][j][k]$

• i 代表前 $ii$ 名考生
• j 代表已经选了 j 名考生
• k 代表之前未选择最小的 Q 。

那么我的状态转移方程就可以变为 $F[i][j][k]=F[i][j][k]+F[i-1][j-1][k]\ast [Q_i>k]F[i][j][k]\; =\; F[i][j][k]\; +\; F[i\; -\; 1][j\; -\; 1][k]\; *\; [Q\_i\; >\; k]$

同时我们在将上次求得的答案继承过来我们就可以得到 $F[i][j][\min (k,Q_i)]+F[i-1][j][k]F[i][j][\backslash min(k\; ,\; Q\_i)]\; +\; F[i\; -\; 1][j][k]$

code