ABC238F Two Exams

题意

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

思路

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

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

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

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

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

那么我的状态转移方程就可以变为 F[i][j][k]=F[i][j][k]+F[i1][j1][k][Qi>k]F[i][j][k] = F[i][j][k] + F[i - 1][j - 1][k] * [Q_i > k]

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

code