P7154 [USACO20DEC] Sleeping Cows P
原题
我们先思考如果没有极大匹配这个限制该怎么做
ysx曾经说过：dp要先考虑递推顺序
看到这个题的限制\(s_i \leq t_i\)，可以想到这题要先按照\(s_i\)和\(t_i\)的顺序排序
不妨设\(dp_{i,j}\)表示考虑了前\(i\)个奶牛和前\(j\)个牛棚的方案书，容易得到\(dp_{i,j}=dp_{i-1,j} + dp_{i-1,j-1}\)
然后我们考虑如果加上了极大匹配的性质要怎么做
我们发现对于一个牛棚\(t_i\)，他能和所有\(s_i \leq t_i\)的奶牛进行匹配(废话)
所以我们就可以发现对于一个牛棚，他不被匹配上的条件是不存在任何一个为被匹配的奶牛\(s_i\)满足\(s_i \leq t_i\)
也说明如果对于某一个奶牛\(s_i\)被钦定为不匹配，那在之后的所有牛棚都必须找一个能与之匹配的奶牛与之匹配(也就是说在这之后的牛棚不能不匹配)
因此我们可以把\(s_i\)和\(t_i\)放在一起排序，假定所有奶牛和牛棚无相等的大小关系
不妨设\(dp_{i,j,k}\)表示考虑所有\(\leq i\)的奶牛和牛棚，其中有\(j\)个未被分配的奶牛和\(k\)个被钦定为不再匹配的奶牛的方案数
- 如果当前是牛棚，可以得到
\[\begin{align}
dp_{i,j,0}&=dp{i-1,j,0}+(j+1) \times dp_{i-1,j+1,0} \\
dp_{i,j,k}&=(j-k+1) \times dp_{i-1,j+1,k} \ (k \neq 0) \\
\end{align}
\]
- 如果当前是奶牛，可以得到
\[\begin{align}
dp_{i,j,0}&=dp_{i-1,j-1,0} \\
dp_{i,j,k}&=dp_{i-1,j-1,k-1} + dp_{i-1,j-1,k} \\
\end{align}
\]
可以发现我们并不在乎当前有多少奶牛被钦定为不匹配，而只在乎是否存在被钦定为不匹配的奶牛
因此第三维可以被压成状态\(0/1\)，并定义\(j\)为有\(j\)个想要被分配而未被分配的奶牛，换言之被钦定为不分配的不算在\(j\)内
可以得到dp柿子：
- 如果当前是牛棚，可以得到
\[\begin{align}
dp_{i,j,0}&=dp{i-1,j,0}+(j+1) \times dp_{i-1,j+1,0} \\
dp_{i,j,k}&=(j+1) \times dp_{i-1,j+1,1} \\
\end{align}
\]
- 如果当前是奶牛，可以得到
\[\begin{align}
dp_{i,j,0}&=dp_{i-1,j-1,0} \\
dp_{i,j,1}&=dp_{i-1,j,0} + dp_{i-1,j,1} + dp_{i-1,j-1,1} \\
\end{align}
\]
最后原题会卡空间，所以只需要加上一个滚动数组优化即可
最终复杂度\(O(n^2)\)