题目意思是,收集卡片,收集每张卡片的概率已经给出,并且所有的概率之和小于或等于1,问你收集完所有卡片的零食袋数的期望。


这题很6啊,状态压缩,利用二进制的特性来枚举,但是有个坑啊,输出要是保留4位小数啊,题目最后说了啊(the standard answer is no more that 10^-4.)。

假设现在一共要收集4张卡。那么:1111就代表收集了4张卡,1001就代表收集到了第一张和第四张卡。接下来关于卡片的我们都以2进制来谈:

那么我们设dp[i](注意,用二进制看i这个数!)为当前收集了i状态卡片后距离收集完所有卡片的期望。如果当然卡片有N张(10进制),那么dp[(1<<N)-1]是不是就是1111的状态?这个状态下已经收集完了所以期望为0。

设p[j]为第j张卡片的概率

如果买一袋零食里面有一张卡片并且当前状态不存在这个卡片,那么这张卡片我们得在当前状态的基础上加上他,就是:∑p[j]*dp[i|(1<<j)

如果买一袋零食里面有一张卡片并且当前已经存在这个卡片,贡献为0,当前状态不变,就是:∑p[j]*dp[i]

如果买一袋零食里面没有卡片,贡献为0,当前状态不变:nop*dp[i](nop代表没有卡片的概率)

所以状态转移方程就是:

dp[i] = dp[i]*(nop+∑p[j])+∑p[j]*dp[i|(1<<j) + 1

整理得:

dp[i] = (∑p[j]*dp[i|(1<<j)+1)/(1-nop-∑p[j])


代码:

StatusAccepted
Time218ms
Memory9948kB
Length795
LangC++
#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int maxn=22;
int n, inf;
double p[maxn], dp[1<<maxn];
double nop;
int main()
{
    while(~scanf("%d", &n)){
        inf=1<<n;
        nop = 1;
        for(int i=0;i<n;i++){
            scanf("%lf", &p[i]);
            nop-=p[i];
        }
        dp[inf-1]=0;
        for(int i=inf-2;i>=0;i--){
            dp[i]=1;
            double g=nop;
            for(int j=0;j<n;j++){
                if((i&(1<<j))==0){    //如果没有当前的卡片则加入拿到这张卡后的期望
                    dp[i]+=p[j]*dp[i|(1<<j)];
                }
                else{               //如果当前卡片已经存在或者没卡
                    g+=p[j];
                }
            }
            dp[i]/=(1-g);
        }
        printf("%.4lf\n", dp[0]);
    }
    return 0;
}