AtCoder Beginner Contest 382-E

发表于 阅读次数： 本文字数： 765 阅读时长 ≈ 3 分钟

Problem

有无数包牌，每包有 $N$ 张牌。在每一包牌中， 第 $i$ 张牌是稀有牌，概率为 $P_i\%$。每张牌是否稀有与其他牌是否稀有无关。

逐一打开包装，并获得每包中的所有卡片。当你一直开包直到总共获得至少 $X$ 张稀有卡牌时，求你开包的预期次数。

Constraints

$1 \leq N \leq 5000,1 \leq X \leq 5000,1 \leq P_i \leq 100$

Solution

该问题可以分为两个部分。

首先，求出开一包卡牌将会得到的稀有卡牌数量的分布列。

这是一个多元二项分布问题，直接暴力计算的话需要枚举一包卡牌的子集。

考虑动态规划。设 $dp{i,j}$ 为一包卡牌内前 $i$ 张牌中存在 $j$ 张稀有牌的概率。$dp{i,j}$ 可由两个状态转移：原本抽到了 $j-1$ 张稀有牌，再翻一张发现正好是稀有牌；原本抽到了 $j$ 张稀有牌，再翻一张发现不是稀有牌。故转移方程为：

其中，$dp{0,0}=1,dp{i,j}=0(j<0)$。

通过上述动态规划得到 $P(开一包卡牌得到j张稀有卡牌)=dp_{n,j}$，将其记作 $Y_j$。

接着解决第二个问题：已知开一包卡牌得到的稀有卡牌数量分布列为 $Y_j$，求开出 $X$ 张稀有牌的期望开包次数。

设得到 $i$ 张稀有牌的期望开包次数是 $E_i$。对于 $i=0$，有 $E_i=0$。模拟一次开包，将会有 $Y_j$ 的概率获得 $j$ 张稀有牌。所以有：

但是这个方程左右两侧都有 $E_i$ 项（$j=0$ 时），所以不能简单的递推。

将式子变换一下：

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#define N 6010

int n,m;
double p[N];
double dp[N][N];
double E[N];
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>p[i],p[i]/=100;
    dp[0][0]=1; //起始条件，抽前0张牌的时候得到0张稀有牌的概率是100%
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            //抽前i张卡牌，正好得到j张稀有牌的概率是dp[i][j]
            if(j==0) dp[i][j]=dp[i-1][j]*(1-p[i]); //防止越界
            else dp[i][j]=dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i]);
        }
    }
    //此时得到了开一次包的概率分布表（得到j张稀有牌）为dp[n][j]
    for(int j=0;j<=n;j++)
    {
//        DEBUG(j,1);
//        DEBUG(dp[n][j],2);
    }
    for(int i=1;i<=m;i++)
    {
        //得到i张稀有牌的期望开包次数是E[i]
        for(int j=1;j<=n;j++)
        {
            if(i-j>=0) E[i]+=(E[i-j])*dp[n][j];
            else E[i]+=(0)*dp[n][j];
        }
        E[i]=(1+E[i])/(1-dp[n][0]);
    }
    cout<<E[m]<<endl;
}