ABC238F Two Exams

 

https://atcoder.jp/contests/abc238/tasks/abc238_f

题意

在一个地方有 $N$ 名考生,共参加了两次考试两次考试的排名分别为 $P_i \ Q_i$ 。现在要求选出 $K$ 名考生,使得这 $K$ 名考生中不存在某位考生的两次排名 $(P_i , Q_i)$ 都比某位未选上的考生的两次排名$(P_j,Q_j)$ 低。

思路

对于该题目我们不妨将这些排名按照第一关键字为 $P_i$ 第二关键字为 $Q_i$ 排序。

我们发现如果在后面的考生想要参选,那么依照我们的排序规则我们已经知道了 $P_i < P_j$ 那么必须满足当前同学的排序 $Q_i > Q_j$ 才可以参选。

由于 $P_i$ 顺序是固定的,那么我们不妨确定最小未选择 $Q_i$ 作为我们的转移条件。

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

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

那么我的状态转移方程就可以变为 $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]$

code

algorithm