【题解】[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$。
题意:
现给定长度均为 $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$。
突然想到马上联赛了,把这么多场模拟赛用到的一些 $\text{tricks}$ 都写下来。
考完自闭了,怎么能这么菜......
这次考试要钉在我的生涯耻辱柱上了,但是为了让自己对自己的水平有一个清楚的认知,还是写下来吧。