一道隐藏很深的水题。。。。。
题目大意
(Nleq 300)
题解
很重要的性质是(B_i<A_i),这保证了(i)不能套在(i)里面。于是我们把所有的(A_i,B_i)放在一起排序,一个(B)点可以和前面任意一个(A)点匹配,我们要求最大匹配的方案数。
考虑遇到一个(B_i)的时候,如果选择和前面某个未匹配的(A_j)匹配,则没有影响,如果选择让它不和前面任何一个未匹配的(A_j)匹配,那么前面所有的未匹配的(A_j)都必须要在后面找到匹配的(B_k),否则就始终有一个匹配(A_j - B_i)未选,使得结果并不是最大匹配了。我们记录一个三维状态(f_{i,j,k}),(i)表示前(i)个点,(j)表示未匹配的(A)点个数,(k)表示由于前面放空某个(B)点而导致必须匹配的(A)点个数(是包括在(j)个未匹配(A)点里的)。
转移很简单,遇到(A)点时直接(j=j+1),遇到(B)点时考虑三种情况:
- 放空这个(B)点,(f[i+1][j][j]leftarrow f[i][j][k])。
- 将这个(B)点与前面某个必须匹配的(A)点匹配,(f[i+1][j-1][k-1]leftarrow f[i][j][k]*k)。
- 将这个(B)点与前面某个非必须匹配的(A)点匹配,(f[i+1][j-1][k]leftarrow f[i][j][k]*(j-k))。
最后(ans=sum_{j=0}^{N}f[tot][j][0]),即不存在必须匹配的(A)点的所有状态。
滚动一下数组节省空间。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=307;
const ll P=1e9+7;
int n,len,l[N],r[N];
ll ans,f[2][N][N];
struct note{int pos,typ;}p[N<<1];
int cmp(note a,note b){return a.pos==b.pos?a.typ<b.typ:a.pos<b.pos;}
int main(){
freopen("ds.in","r",stdin);
//freopen("ds.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d%d",&r[i],&l[i]),p[++len]=(note){l[i],0},p[++len]=(note){r[i],1};
sort(p+1,p+len+1,cmp);
f[0][0][0]=1;
for(int i=0,a=0,b;i<len;++i,a^=1){
b=a^1;memset(f[b],0,sizeof(f[b]));
if(p[i+1].typ){
for(int j=0;j<=n;++j)for(int k=0;k<=j;++k)if(f[a][j][k]>0)f[b][j+1][k]=(f[b][j+1][k]+f[a][j][k])%P;
}else{
for(int j=0;j<=n;++j)for(int k=0;k<=j;++k)if(f[a][j][k]>0){
if(j>0){
f[b][j-1][k]=(f[b][j-1][k]+f[a][j][k]*(j-k))%P;
if(k>0)f[b][j-1][k-1]=(f[b][j-1][k-1]+f[a][j][k]*k)%P;
}
f[b][j][j]=(f[b][j][j]+f[a][j][k])%P;
}
}
}
ans=0;
for(int j=0;j<=n;++j)ans=(ans+f[len&1][j][0])%P;
printf("%lld
",ans);
return 0;
}