【题解】[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$。
考虑将 $s$ 与 $t$ 都从小到大排序，那么对于一个 $t_i$，能与之匹配的 $s_j$ 应该是 $s$ 的一段前缀。
那么考虑从小到大讨论每一个 $t$，每一个 $t$ 有两种选择：选择一个合法的 $s$ 与之匹配，或放弃将这个 $t$ 加入匹配。
不难发现，当我们将 $t$ 升序排序后，对于一个 $s_j$，若其可与 $t_i$ 匹配，那么一定可以与 $t_{i+1}$ 匹配。此时考虑什么情况下，我们才可以选择放弃将当前的 $t$ 加入匹配。
若当前 $t_i$ 所能匹配的 $s$ 的最大下标为 $\text{lim}_ i$，那么若要放弃 $t_i$，则 $s_1$ 到 $s_{\text{lim}_ i}$ 均需要被匹配。因为如果放弃 $t_i$ 且放弃 $s_1$ 到 $s_{\text{lim}_ i}$ 中的任意一个，那么他们一定可以组成一个新的匹配对，这是我们不希望看到的。
也就是说，当存在一个 $s_i$ 被放弃加入匹配时，任意满足 $i\le \text{lim}_ j$ 的 $t_j$ 都不可以被放弃。
同时，我们实际上只关注最小的，被放弃的 $s_i$。那么一个 $\mathcal{O}(n^3)$ 的算法就很显然了：
考虑最小的被放弃的 $s_i$ 是谁，那么对于任意 $j < i$ 的 $s_j$ 都需要加入匹配，$\text{lim}_ j \ge i$ 的 $t_j$ 均不能放弃。$\mathcal{O}(n)$ 枚举 $s_i$ 后可以通过 $\mathcal{O}(n^2)$ 的 $\text{dp}$ 解决。
考虑在这个思路上进行优化。实际上，我们并不需要枚举 $s_i$ 是谁，而是只关心 $s$ 的一个前缀是否全部加入了匹配。也就是说，我们可以将上面枚举 $s_i$ 的过程转变为一个 $\text{bool}$ 变量 $0/1$ 表示某一个前缀是否全部选入。
那么可以维护两个指针，分别指向当前还未考虑的最小的 $s$ 与 $t$，每次选择较小的一边进行更新，特殊地，对于 $s=t$ 的情形，则优先更新 $s$ 一边。
更简单的实现方法，可以将两个数组合并为一个，进行双关键字排序，依次分类讨论更新即可。以下的 $\text{dp}$ 均在这个新的数组上进行讨论。
考虑 $\text{dp}$，设 $\text{dp}_ {i,j,0/1}$ 表示考虑到第 $i$ 个位置，目前有 $j$ 个被选入匹配，但是还未选定匹配谁的 $s$，$1$ 到 $i-1$ 位置中的 $s$ 是否都被选择加入的方案数，其中第三位的 $1$ 表示前缀中的 $s$ 全部加入匹配。
那么可以分类进行转移：
若第 $i$ 个位置是 $s$ 中的元素，那么：
$$\text{dp}_ {i,j,0}=\text{dp}_ {i-1,j-1,0}+\text{dp}_ {i-1,j,0}+\text{dp}_ {i-1,j,1}$$
$$\text{dp}_ {i,j,1}=\text{dp}_ {i-1,j-1,1}$$
可以考虑是否将这个 $s$ 加入匹配，若加入，则 $j\leftarrow j+1$ ，否则不变。需要注意的是若选择放弃当前 $s$ 则第三位必然为 $0$。
若第 $i$ 个位置是 $t$ 中的元素，那么：
$$\text{dp}_ {i,j,0}=\text{dp}_ {i-1,j+1,0}\times (j+1)$$
$$\text{dp}_ {i,j,1}=\text{dp}_ {i-1,j,1}+\text{dp}_ {i-1,j+1,1}\times (j+1)$$
若当前第三位为 $0$，那么不能放弃当前 $t$，$j\leftarrow j-1$，同时从当前所有还未确定的 $s$ 中选择一个与当前 $t$ 匹配；若第三位为 $1$，则可以选择放弃当前位，同样也可以选择进行一次匹配。
最后的答案就是：
$$\text{dp}_ {n,0,0}+\text{dp}_ {n,0,1}$$
也就是最后没有在匹配中，却未选择与谁匹配的 $s$。
时间复杂度 $\mathcal{O}(n^2)$。
$\texttt{Code:}$
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;
//#define FILE
#define int long long
#define debug(x) cout << #x << " = " << x << endl
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define LINE() cout << "LINE = " << __LINE__ << endl
#define LL long long
#define ull unsigned long long
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fst first
#define scd second
#define inv(x) qpow((x),mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define vec vector
const int MAXN = 6010;
const int INF = 2e9;
const double PI = acos(-1);
const double eps = 1e-6;
const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;
int n, m;
int dp[2][MAXN][2]; //dp[i][j][0/1] 还有j头牛需要加入，是否填满
int now, pre = 1;//滚动数组
pii s[MAXN];
template<typename T> inline bool read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
a *= f;
return 1;
}
template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}
signed main () {
#ifdef FILE
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
read(n);
for(int i = 1; i <= n; ++i) read(s[i].fst), s[i].scd = 0;
for(int i = 1; i <= n; ++i) read(s[i + n].fst), s[i + n].scd = 1;
sort(s + 1, s + n * 2 + 1);
dp[now][0][1] = 1;
for(int i = 1; i <= n * 2; ++i) {
swap(now, pre);//滚动数组
memset(dp[now], 0, sizeof dp[now]);
if(!s[i].scd) {//若当前是 s 中元素
for(int j = 0; j <= n; ++j) {
if(j) (dp[now][j][0] += dp[pre][j - 1][0]) %= mod;
if(j) (dp[now][j][1] += dp[pre][j - 1][1]) %= mod;
(dp[now][j][0] += dp[pre][j][0] + dp[pre][j][1]) %= mod;
}
} else {//若当前是 t 中元素
for(int j = 0; j <= n; ++j) {
(dp[now][j][1] += dp[pre][j][1]) %= mod;
(dp[now][j][1] += dp[pre][j + 1][1] * (j + 1) % mod) %= mod;
(dp[now][j][0] += dp[pre][j + 1][0] * (j + 1) % mod) %= mod;
}
}
}
printf("%lld\n", ((dp[now][0][0] + dp[now][0][1]) % mod + mod) % mod);
return 0;
}