首页 > 代码库 > Bzoj3622 已经没有什么好害怕的了

Bzoj3622 已经没有什么好害怕的了

2024-08-17 20:48:42   224人阅读

 

这题的题面全是图，而博客园的图随时有挂的危险……

反正能去BZOJ找原题，已经没什么好害怕的了

3622: 已经没有什么好害怕的了

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 476  Solved: 231

Description

技术分享

Input

技术分享

Output

技术分享

Sample Input

4 2
5 35 15 45
40 20 10 30

Sample Output

4

HINT

 

技术分享


输入的2*n个数字保证全不相同。


还有输入应该是第二行是糖果，第三行是药片

 

 

Source

2014湖北省队互测week2

 

丧心病狂的动态规划+容斥原理。

一般看到是省队级别的题我就怂了，然而这题题面太清奇，忍不住想做……绞尽脑汁看题解终于想明白了

 

先把两个数列a，b从小到大排序。

设f[i][j]表示前i对数中，满足糖果大于药片的对数“至少”有j对的方案数。

总共要组n对数，其中糖果大于药片的组数比药片大于糖果的组数多k组，那么总共需要 m=(n+k)/2 对数满足糖果大于药片，剩下的满足药片大于糖果。

 

先用next[]数组记录对于a中的每个数，在j中有next[i]个数比它小，则a[i]可以和next[i]个数组成糖果大于药片的数对。

进行DP： f[i][j]=(f[i-1][j]+f[i-1][j-1]*max(next[i]-(j-1),0)%mod

 

这样求出来的是“至少”有j对的方案数，而我们需要的是“恰好”有m对的方案数。

显然（并不）这是一个容斥问题：

f[n][i]表示总共n对数中，至少有i对数满足“糖果大于药片”。在a数列中，剩下的(n-i)个数各自要找b数列中剩下的一个数配对，方案共有 (n-i)!  (←阶乘) 种。

设dp[n][i]=“n对数中恰好i对数满足糖果大于药片”的方案数，则dp[n][i] = f[n][i]*(n-i)! -多余部分

接下来分析多余部分：

若j>i,在dp[n][j]中(这里的dp[n][j]是已经算完的正确答案，为此需要倒序计算)的一部分可能会被算进f[n][i]中，这种误算的方案有C[j][i]*dp[n][j]种。

所以： dp[n][i]=f[n][i]*(n-i)! - ( Σ(i<j<=n)   C[j][i]*dp[n][j] )  注意取模

之后发现dp数组只用到了[n][i]，所以第一维可以扔掉了

 

这可能是我至今写过最长的分析了

 

もう何も怖くない...じゃねよ！

 

 1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #define LL long long 9 using namespace std;10 const int mod=1e9+9;11 const int mxn=2010;12 int read(){13     int x=0,f=1;char ch=getchar();14     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}15     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}16     return x*f;17 }18 int n,m;19 int a[mxn],b[mxn];//糖果和药片 20 int nxt[mxn];21 LL f[mxn][mxn];//前[i]组中，有[j]组糖果数大于药片数 22 LL dp[mxn];23 LL c[mxn][mxn],jc[mxn];24 void clc(){25     int i,j;26     for(i=0;i<=n;i++)c[i][0]=1;27     for(i=1;i<=n;i++)28      for(j=1;j<=i;j++)29          c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;30     jc[1]=1;31     for(i=2;i<=n;i++)jc[i]=jc[i-1]*i%mod;32     return;33 }34 int main(){35     n=read();m=read();36     m=(m+n)/2;37     int i,j;38     for(i=1;i<=n;++i)a[i]=read();39     for(i=1;i<=n;++i)b[i]=read();40     sort(a+1,a+n+1);41     sort(b+1,b+n+1);42     for(i=1,j=1;i<=n;i++){43         for(;j<=n && b[j]<a[i];j++);44         nxt[i]=j-1;45     }46     clc();47     //init48     for(i=0;i<=n;i++)f[i][0]=1;49     for(i=1;i<=n;i++)50      for(j=1;j<=i;j++){51          f[i][j]=(f[i-1][j]+f[i-1][j-1]*max(nxt[i]-j+1,0))%mod;52      }53     for(i=n;i>=m;--i){54         dp[i]=f[n][i]*jc[n-i]%mod;55         for(j=i+1;j<=n;++j){56             dp[i]=((dp[i]-dp[j]*c[j][i]%mod)+mod)%mod;57         }58     }59     60     printf("%lld\n",dp[m]);61     return 0;62 }

 

Bzoj3622 已经没有什么好害怕的了


联系
我们