[题解] 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，保证了合法状态方便转移。