[题解] P7154 [USACO20DEC] Sleeping Cows P
解题报告
有 \(n\) 头奶牛和 \(n\) 个牛棚，一个奶牛 \(u_i\) 能进入一个牛棚 \(v_i\) 当且仅当 \(s_{u_i}\leq t_{v_i}\)，一个牛棚最多只能容纳一头牛。
定义一个完美匹配为：对于所有未分配的奶牛，都不能有任何一个未匹配的牛棚满足条件，求完美匹配的方案数。
关键是找到那些没有匹配的牛棚来计算。
考虑把 \(s\) 和 \(t\) 都放到一起排序，这样做的好处就是：对于一个牛棚，如果前面有不需要匹配的牛，那么这个牛棚必须匹配一头牛。
于是设计状态为 \(f[i,j,0/1]\) 表示当前考虑了前 \(i\) 个元素，有 \(j\) 头牛准备被分配到牛棚里但是还没有分配，\(0/1\) 表示有没有丢掉牛（不匹配的牛），\(0\) 表示有，\(1\) 表示没有。
注意：\(j\) 和第三维的 \(0/1\) 没有任何关系。
初始为 \(f[0][0][1]=1\)，因为任何牛都没有丢掉。
状态转移
设考虑到了第 \(i\) 个位置。
- 第 \(i+1\) 位置为牛。
\(f[i,j,0]->f[i+1,j+1,0],f[i+1,j,0]\)
\(f[i,j,1]->f[i+1,j+1,1],f[i+1,j,0]\)
分为下一轮丢没丢奶牛进行考虑。
- 第 \(i+1\) 个位置为牛棚。
\(j\times f[i,j,0]->f[i+1,j-1,0]\)
\(j\times f[i,j,1]->f[i+1,j-1,1]\)
\(f[i,j,1]->f[i+1,j,1]\)
前两种情况是考虑把当前需要分配的 \(j\) 头牛分配进去。
第三种情况是这个牛棚直接作废。
注意：如果当前丢掉了一些奶牛，那么这个牛棚必须被填满，所以 \(f[i,j,0]\) 是无法转移到 \(f[i+1,j,0]\) 的。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template <typename T>
inline T read(){
T x=0;char ch=getchar();bool fl=false;
while(!isdigit(ch)){if(ch=='-')fl=true;ch=getchar();}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+(ch^48);ch=getchar();
}
return fl?-x:x;
}
#define LL long long
const int maxn = 3000 + 10;
const int P = 1e9 + 7;
struct node{
int val,type;
bool operator <(const node &x)const{
if(val!=x.val)return val<x.val;
return type<x.type;
}
}a[maxn<<1];
int s[maxn],t[maxn],n;
int f[maxn<<1][maxn][2],ans;
inline void add(int &a,int b){
a+=b;
if(a>=P)a-=P;
}
#define read() read<int>()
int main(){
n=read();
for(int i=1;i<=n;i++)s[i]=read(),a[i]=(node){s[i],0};
for(int i=1;i<=n;i++)t[i]=read(),a[i+n]=(node){t[i],1};
sort(a+1,a+1+n*2);
f[0][0][1]=1;
for(int i=0;i<n*2;i++){
if(a[i+1].type==0){
for(int j=0;j<=n+1;j++){
add(f[i+1][j+1][0],f[i][j][0]);
add(f[i+1][j][0],f[i][j][0]);
add(f[i+1][j+1][1],f[i][j][1]);
add(f[i+1][j][0],f[i][j][1]);
}
}
else {
for(int j=0;j<=n+1;j++){
if(j>0)add(f[i+1][j-1][0],1LL*j*f[i][j][0]%P);
if(j>0)add(f[i+1][j-1][1],1LL*j*f[i][j][1]%P);
add(f[i+1][j][1],f[i][j][1]);
}
}
}
ans=f[n*2][0][0]+f[n*2][0][1];ans%=P;
printf("%d\n",ans);
return 0;
}
小结
核心是放在一起排序DP，保证了合法状态方便转移。