动态规划优化

题目链接:P7154 [USACO20DEC] Sleeping Cows P

题意:

现给定长度均为 $n$ 的数组 $s_i$ 与 $t_i$,$s_i$ 能与 $t_j$ 匹配当且仅当 $s_i\le t_j$。一组匹配是极大的,当且仅当对于任意一个匹配对 $(s_i,t_j)$ 均满足 $s_i\le t_j$ ,且任意未被匹配的 $s$ 与 $t$ 中无法再组成匹配对。

求所有极大匹配的方案数。

$n\le 3000,s_i,t_i\le 10^9$。

- 阅读剩余部分 -