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]$
PREVIOUSRange Sums
NEXT连珠线