主要是状态设计比较难想，但其实可以理性地推出来。
P7154 [USACO20DEC] Sleeping Cows P
考虑最终一个合法状态是怎么样的：一定是一堆小牛棚，一堆大奶牛，最大的牛棚小于最小的奶牛。
这启发我们将所有牛和牛棚放在一起，那么一定先选择牛棚，后选择奶牛。
我们加入一个牛棚后的决策情况：
- 将这个牛棚与前面准备匹配但没有匹配的牛匹配，需要记录前面有多少牛。
- 将这个牛棚抛弃，这需要保证前面没有被抛弃的奶牛。
加入一头牛的抉择情况：
- 将这个奶牛加入匹配之列。
- 将这个奶牛抛弃。
那么设 \(dp_{i,j,0/1}\) 表示到（混合后）第 \(i\) 个为止，在匹配队列中的奶牛有 \(j\) 头，是否有奶牛已经被抛弃的方案数。
\(\bigstar\texttt{Attention}\)：注意排序的时候要将相同大小的物品奶牛放在前面。
#define Maxn 6005
#define mod 1000000007
int n,cnt;
int dp[Maxn][Maxn][2];
struct Object
{
int opt,val;
Object(int Opt=0,int Val=0):opt(Opt),val(Val){}
bool friend operator < (Object x,Object y)
{ return (x.val!=y.val)?(x.val<y.val):(x.opt<y.opt); }
}a[Maxn];
int main()
{
n=rd();
for(int i=1,x;i<=n;i++) x=rd(),a[++cnt]=Object(0,x);
for(int i=1,x;i<=n;i++) x=rd(),a[++cnt]=Object(1,x);
sort(a+1,a+cnt+1),dp[0][0][0]=1;
for(int i=1;i<=cnt;i++) for(int j=0;j<=i;j++)
{
if(a[i].opt)
{
dp[i][j][0]=1ll*dp[i-1][j+1][0]*(j+1)%mod;
dp[i][j][1]=1ll*dp[i-1][j+1][1]*(j+1)%mod;
(dp[i][j][0]+=dp[i-1][j][0])%=mod;
}
else
{
if(j) dp[i][j][0]=dp[i-1][j-1][0];
if(j) dp[i][j][1]=dp[i-1][j-1][1];
(dp[i][j][1]+=(1ll*dp[i-1][j][0]+1ll*dp[i-1][j][1])%mod)%=mod;
}
}
printf("%d\n",(dp[cnt][0][0]+dp[cnt][0][1])%mod);
return 0;
}