NKOJ 2127 搜集卡片 （数学期望+状态压缩+递推）

发表于 |
字数统计: 533字 | 阅读时长 ≈ 2min

P2127【概率】搜集卡片

问题描述

童年时代，你是否热衷于搜集零食里的卡片呢？比如你集齐了108张水浒英雄的卡片，你会感到非常有成就感，而且还可以去兑换奖品。

作为一个聪明的小孩，你注意到如果你要赢得奖品，你必须买很多很多的零食才能搜集齐卡片。要赢得奖品，你估计要买多少袋零食才能成功？

输入格式

第一行，一个整数N(1 <= N <= 20), 表示总共有N种不同的卡片。
第二行，N个空格间隔的实数p1, p2, …, pN, (p1 + p2 + … + pN <= 1), 表示零食袋中每种卡片出现的概率。
注意：一包零食中最多有一张卡片，也可能一张都没有。

输出格式

一个实数，表示你计算的结果，保留6位小数

样例输入

2
0.1 0.4

样例输出

10.500000

注意到n的范围，容易想到状态压缩。
用一个二进制数$S$表示当前已收集到的卡片集合。
用$F[S]$表示从状态$S$开始，收集完所有卡片需要买的零食的期望值。
那么买一袋零食，有
$$F[S]=1+(1-\sum {p[i]})\times F[S]+\sum{p[j]\times F[ \ S|\ j\ ]}+\sum {p[k]\times F[S]}$$
其中$i取1-n，表示没抽中卡片，j表示一个不在S集合中的卡片，k表示在集合S中的卡片$
于是移项整理得到
$$\sum{p[i]}\times F[S]=1+\sum{F[\ S|\ j\ ]\times p[j]}$$
其中$i和j都表示不在集合S中的卡片$
于是直接递推即可。目标状态是$F[0]$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int n,S;
double P[22],F[1050000],tmp;
int main()
{
	int i,j;
	scanf("%d",&n);S=(1<<n)-1;
	for(i=1;i<=n;i++)scanf("%lf",&P[i]);
	for(i=S-1;i>=0;i--)
	{
		tmp=0;F[i]=1;
		for(j=1;j<=n;j++)
		if(!(i&(1<<j-1)))
		{
			F[i]+=F[i|(1<<j-1)]*P[j];
			tmp+=P[j];
		}
		F[i]/=tmp;
	}
	printf("%.6lf",F[0]);
}