首页 > 代码库 > BZOJ3622已经没有什么好害怕的了
BZOJ3622已经没有什么好害怕的了
Description
.jpg)
Input
.jpg)
Output
.jpg)
Sample Input
4 2
5 35 15 45
40 20 10 30
5 35 15 45
40 20 10 30
Sample Output
4
HINT
.jpg)
输入的2*n个数字保证全不相同。
还有输入应该是第二行是糖果，第三行是药片
题解：
记得以前在学校题库中做过这道题。
先判断k是否可能实现，若能，求出需要有恰好多少对糖果比巧克力大。
现将两组数各自从小到大排序。用dp[i,j]表示给前i个糖果中的j个安排数值更低的的巧克力的方案数。
设第i个糖果比前k个巧克力数值大，则除了dp[i,j]<——dp[i-1,j]外，另一种转移方式为dp[i,j]<——dp[i-1,j-1]*(k-(j-1))。
预处理好后，设g[i]=dp[n,i]*(n-i)!，即任意安排剩下的n-i对糖果与巧克力。可能会有重复方案，其中恰好j对糖果比巧克力大的方案会重复c(j,i)次（j>=i）。
设ans[i]为恰好i对糖果比巧克力大的方案数。
从上向下枚举i，ans[i]=g[i]-∑(ans[j]*c(j,i))（j>=i）。
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 int c[2005][2005],a[2005],b[2005],dp[2005][2005],g[2005],jc[2005]; 4 int mo=1000000009; 5 int main() 6 { 7 int n,k; 8 scanf("%d%d",&n,&k); 9 if((n-k)%2!=0){ printf("0\n"); return 0; }10 k=(n-k)/2; k=n-k;11 for(int i=1;i<=n;i++)scanf("%d",&a[i]);12 for(int i=1;i<=n;i++)scanf("%d",&b[i]);13 sort(a+1,a+n+1); sort(b+1,b+n+1);14 b[0]=-2000000000; b[n+1]=2000000000; 15 int l=0; dp[0][0]=1;16 for(int i=1;i<=n;i++)17 {18 while(b[l+1]<a[i])l++;19 for(int j=0;j<=min(i,l);j++)20 {21 if(j)dp[i][j]=(1ll*(l-(j-1))*dp[i-1][j-1])%mo;22 dp[i][j]=(dp[i][j]+dp[i-1][j])%mo;23 }24 }25 c[0][0]=1;26 for(int i=1;i<=n;i++)27 {28 c[i][0]=1; c[i][i]=1;29 for(int j=1;j<=i-1;j++)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mo;30 }31 jc[1]=1;32 for(int i=2;i<=n;i++)jc[i]=(1ll*jc[i-1]*i)%mo;33 g[n]=dp[n][n];34 for(int i=n-1;i>=0;i--)35 {36 g[i]=(1ll*dp[n][i]*jc[n-i])%mo;37 for(int j=i+1;j<=n;j++)g[i]=(1ll*g[i]-1ll*g[j]*c[j][i])%mo;38 }39 printf("%d\n",(g[k]+mo)%mo);40 }41 42
BZOJ3622已经没有什么好害怕的了
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。