首页 > 代码库 > BZOJ4221 : JOI2012 kangaroo
BZOJ4221 : JOI2012 kangaroo
将袋鼠大小和口袋大小分别从小到大排序。
枚举从左往右第一只没有被放入任何口袋的袋鼠$x$，那么$x$之前的所有袋鼠、以及$x$能装入的所有口袋都应该在匹配边上。
按这只袋鼠将上下两个序列分为两部分，设$f[i]$表示左边内部有$i$条匹配边的方案数，$g[i]$表示右边内部有$i$条匹配边的方案数。
那么枚举左右各剩下$i$个点未匹配，则对答案的贡献是$f[L-i]\times g[R-i]\times i!$。
对于$f,g$的求解，假设是求$f$，那么从右往左考虑每个袋鼠，限制会越来越松。
所以设$dp[i][j]$表示考虑了$i$开始到最后一只袋鼠，目前有$j$条匹配边的方案数。
对于第$i-1$只袋鼠，它可选的匹配边条数是固定的，减去$j$就是它匹配某个口袋的方案数。
时间复杂度$O(n^3)$。
#include<cstdio>#include<algorithm>const int N=305,P=1000000007;int n,i,j,ca,cb,l,r,a[N],b[N],A[N],B[N],fac[N],f[N],g[N],dp[N][N],ans;inline void up(int&a,int b){a+=b;if(a>=P)a-=P;}inline void dpl(){ int i,j,k,o; for(i=1;i<=ca+1;i++)for(j=0;j<=ca;j++)dp[i][j]=0; dp[ca+1][0]=1; for(i=ca;i;i--){ for(k=0,o=cb;o;o--)if(A[i]<B[o])k++;else break; for(j=0;j<=ca;j++)if(dp[i+1][j]){ up(dp[i][j],dp[i+1][j]); up(dp[i][j+1],1LL*dp[i+1][j]*(k-j)%P); } } for(l=ca,i=0;i<=ca;i++)f[i]=dp[1][i];}inline void dpr(){ int i,j,k,o; for(i=0;i<=cb;i++)for(j=0;j<=cb;j++)dp[i][j]=0; dp[0][0]=1; for(i=1;i<=cb;i++){ for(k=0,o=1;o<=ca;o++)if(A[o]<B[i])k++;else break; for(j=0;j<=cb;j++)if(dp[i-1][j]){ up(dp[i][j],dp[i-1][j]); up(dp[i][j+1],1LL*dp[i-1][j]*(k-j)%P); } } for(r=cb,i=0;i<=cb;i++)g[i]=dp[cb][i];}int main(){ scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]); std::sort(a+1,a+n+1),std::sort(b+1,b+n+1); for(fac[0]=i=1;i<=n;i++)fac[i]=1LL*fac[i-1]*i%P; for(i=1;i<=n;i++){ ca=cb=0; for(j=1;j<i;j++)A[++ca]=a[j]; for(j=1;j<=n;j++)if(b[j]<=a[i])B[++cb]=b[j]; dpl(); ca=cb=0; for(j=i+1;j<=n;j++)A[++ca]=a[j]; for(j=1;j<=n;j++)if(b[j]>a[i])B[++cb]=b[j]; dpr(); for(j=0;j<=l&&j<=r;j++)up(ans,1LL*f[l-j]*g[r-j]%P*fac[j]%P); } return printf("%d",ans),0;}
BZOJ4221 : JOI2012 kangaroo
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。