HDU4336 / Card Collector

Posted on By 二价氢

题目:HDU 4336

给你N张卡片(和一张空白卡片),每张卡片抽到的概率为,问抽齐所有卡片的期望抽卡次数(课课课,不课金还是人?)

一遍有两种做法,一为容斥原理,二为由后至前的概率DP

这里提供第三种做法,由前往后的概率DP(算贡献)

首先假设最开始的时候持有一张空白卡片

考虑当前状态为状态,到达此状态的概率为,持有卡片集合,剩下卡片集合

对于这个状态,它能够转移到下一个状态的抽卡期望为:

其中,k为持有卡片的概率之和,由等比差数列求和的方法,可以知道

接下来我们算贡献

设到达状态的抽卡期望为,则对于能转移到的状态(即状态抽到卡片),的贡献为

即转移到下一状态中,这个状态的概率

而抽卡次数的贡献为

同时,可以计算出此状态的概率对到达下一状态的概率的贡献为

AC-Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 20 + 5;
double p[maxn];
double dp[(1 << 20) + 5];
double w[(1 << 20) + 5];
int n;
double sqr(double x) {return x * x;}
void work()
{
    p[0] = 1;
    for (int i = 1 ; i <= n ; i ++)
    {
        scanf("%lf" , &p[i]);
        p[0] -= p[i];
    }
    memset(w , 0 , sizeof(w));
    memset(dp , 0 , sizeof(dp));
    w[0] = 1;
    for (int i = 0 ; i < (1 << n) ; i ++)
    {
        double k = p[0];
        for (int j = 0 ; j < n ; j++)
            k += p[j + 1] * ((i & (1 << j)) != 0);
        for (int j = 0 ; j < n ; j++)
        {
            if ((i & (1 << j)) == 0)
            {
                w[i | (1 << j)] += w[i] * p[j + 1] / (1 - k);
                dp[i | (1 << j)] += p[j + 1] * dp[i] / (1 - k) + w[i] * p[j + 1] / sqr(1 - k);
                // 算贡献
            }
        }
    }
    printf("%.6lf\n",dp[(1 << n) - 1]);
}
int main()
{
    while (~scanf("%d" , &n))
        work();
    return 0;
}