题解：CF229E Gifts

· · 题解

不赖的 DP 加组合数学题。

首先我们先将所有礼物排序，找出第 n 大的礼物，其价值为 v，显然价值大于 v 的礼物都必须被选，而价值等于这 v 的有很多种方案选择。设价值等于 v 的礼物有 cnt 个，我们需要选择的价值等于 v 的礼物有 res 个，方案总数就是 \binom{cnt}{res}。

设 DP 状态 dp_{i,j} 为前 i 个名字中选择了 j 个价值为 v 的礼物。

那么如果一个名字中没有价值为 v 的礼物，其转移如下：dp_{i,j}=\dfrac{dp_{i-1,j}}{\binom{k_i}{nd_i}}，其中 nd_i 表示第 i 个名字中价值大于 v 的礼物的数量。

否则其中只有一个价值为 v 的礼物（如果有两个及以上，则不满足“不会出现名称和价值都相同的礼物”），此时可以选或不选这个礼物，转移如下：dp_{i,j}=\dfrac{dp_{i-1,j}}{\binom{k_i}{nd_i}}+\dfrac{dp_{i-1,j-1}}{\binom{k_i}{nd_i+1}}。

最后我们还需要除以方案的总数，所以答案是 \dfrac{dp_{m,res}}{\binom{cnt}{res}}。

下附代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
int n,m,num[1005],c[1005][1005],q[1005],cnt,res,tot;
double C[1005][1005],dp[1005][1005];
void getC(){
    C[0][0]=1;
    for(int i=1;i<=1000;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++){
            C[i][j]=C[i-1][j]+C[i-1][j-1];
        }
    }
}
bool cmp(int x,int y){
    return x>y;
}
signed main(){
    cin>>n>>m;getC();
    for(int i=1;i<=m;i++){
        cin>>num[i];
        for(int j=1;j<=num[i];j++) cin>>c[i][j],q[++tot]=c[i][j];
    }
    sort(q+1,q+tot+1,cmp);
    for(int i=1;i<=tot;i++) if(q[i]==q[n]) cnt++;
    for(int i=1;i<=n;i++) if(q[i]==q[n]) res++;
    dp[0][0]=1;
    for(int i=1;i<=m;i++){
        bool flag=0;int nd=0;
        for(int j=1;j<=num[i];j++){
            if(c[i][j]==q[n]) flag=1;
            if(c[i][j]>q[n]) nd++;
        }
        if(!flag){
            for(int j=0;j<=res;j++) dp[i][j]=dp[i-1][j]/C[num[i]][nd];
        }else{
            for(int j=0;j<=res;j++){
                dp[i][j]=dp[i-1][j]/C[num[i]][nd];
                if(j>0) dp[i][j]+=dp[i-1][j-1]/C[num[i]][nd+1];
            }
        }
    }
    printf("%.10lf\n",dp[m][res]/C[cnt][res]);
    return 0;
}