ABC238F Two Exams
题意
在一个地方有 N 名考生,共参加了两次考试两次考试的排名分别为 Pi Qi 。现在要求选出 K 名考生,使得这 K 名考生中不存在某位考生的两次排名 (Pi,Qi) 都比某位未选上的考生的两次排名(Pj,Qj) 低。
思路
对于该题目我们不妨将这些排名按照第一关键字为 Pi 第二关键字为 Qi 排序。
我们发现如果在后面的考生想要参选,那么依照我们的排序规则我们已经知道了 Pi<Pj 那么必须满足当前同学的排序 Qi>Qj 才可以参选。
由于 Pi 顺序是固定的,那么我们不妨确定最小未选择 Qi 作为我们的转移条件。
那么我们的方程就变成 F[i][j][k]
i
代表前 i 名考生
j
代表已经选了 j
名考生
k
代表之前未选择最小的 Q
。
那么我的状态转移方程就可以变为 F[i][j][k]=F[i][j][k]+F[i−1][j−1][k]∗[Qi>k]
同时我们在将上次求得的答案继承过来我们就可以得到 F[i][j][min(k,Qi)]+F[i−1][j][k]
code