Problem

bzoj

題意：給定\(n\)只袋鼠，每只袋鼠有倆屬性\(a,b\)，若\(a_i\leq b_j\)，則\(i\)是可以被\(j\)放置在袋子里的，求經(jīng)過(guò)一系列放置操作后無(wú)法進(jìn)行操作時(shí)的狀態(tài)有多少種可能（每只袋鼠只能被一只袋鼠放在袋子里，同時(shí)也只能放一只袋鼠在袋子里）

\(n\leq 300,\forall i\in[1,n]a_i\geq b_i\)

Solution

將每只袋鼠拆成出點(diǎn)和入點(diǎn)后做匹配，相當(dāng)于剩余未匹配點(diǎn)中\(\min a\geq \max b\)的匹配方案數(shù)

由于\(a_i\geq b_i\)保證不可能自己連向自己，相當(dāng)于是自由匹配，所以點(diǎn)與點(diǎn)之間的順序是沒(méi)有任何關(guān)系的，考慮將兩者從大到小排序

設(shè)\(f[i][j][k]\)表示當(dāng)前考慮到第\(i\)只袋鼠的體積，這\(i\)只袋鼠中有\(j\)只已經(jīng)被匹配，設(shè)\(t\)為第\(i\)只袋鼠能塞進(jìn)的最小口袋（\(t\)也遞增），則\(k\)表示前\(t\)個(gè)口袋中與袋鼠\([i+1,n]\)中匹配的數(shù)量

考慮到在定義下的\(f[i][j][k]\)中，這\(j\)只已經(jīng)被匹配的袋鼠所對(duì)應(yīng)的口袋一定在區(qū)間\([1,t]\)中，所以口袋\([1,t]\)分為三類(lèi)：

• ① 和區(qū)間\([1,i]\)內(nèi)共\(j\)只袋鼠匹配的口袋，共\(j\)個(gè)
• ② 和區(qū)間\([i+1,n]\)內(nèi)共\(k\)只袋鼠匹配的口袋，共\(k\)個(gè)
• ③ 自由節(jié)點(diǎn)，尚未匹配，共\(t-j-k\)個(gè)

理順了這些可以得到以下仨轉(zhuǎn)移式（一般自己寫(xiě)可能會(huì)有情況缺漏，反正我是想了很久）

\[f[i][j][t-j]+=f[i-1][j][k]\]

\[f[i][j+1][k]+=f[i-1][j][k]\cdot (t-j-k)\]

\[f[i][j+1][k-1]+=f[i-1][j][k]\cdot k\]

自然統(tǒng)計(jì)答案

\[Ans=\sum_{i=0}^nf[n][i][0]\]

Code

#include <bits/stdc++.h> using namespace std; #define rg registertemplate <typename _Tp> inline _Tp read(_Tp&x){char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();while(isdigit(c11))x=x*10+c11-'0',c11=getchar();return x; }const int N=301,p=1e9+7; int f[N][N][N],a[N],b[N]; int n,ans;template <typename _tp> inline void pls(int&A,_tp B){A=A+B<p?A+B:A+B-p;} inline bool cmp(const int&A,const int&B){return A>B;}void init();void work();void print(); int main(){init();work();print();return 0;}void work(){f[0][0][0]=1;for(rg int i=1,t=1;i<=n;++i){if(!t)++t;while(a[i]<b[t]&&t<=n)++t;--t;for(rg int j=0;j<i;++j)for(rg int k=0;k+j<=t;++k){pls(f[i][j][t-j],f[i-1][j][k]);pls(f[i][j+1][k],1ll*f[i-1][j][k]*(t-j-k)%p);if(k)pls(f[i][j+1][k-1],1ll*f[i-1][j][k]*k%p);}} }void print(){for(rg int i=0;i<=n;++i)pls(ans,f[n][i][0]);printf("%d\n",ans); }void init(){read(n);for(rg int i=1;i<=n;++i)read(a[i]),read(b[i]);sort(a+1,a+n+1,cmp);sort(b+1,b+n+1,cmp); }

轉(zhuǎn)載于:https://www.cnblogs.com/penth/p/9779072.html

總結(jié)

以上是生活随笔為你收集整理的题解-bzoj4221 JOI2012kangaroo的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。