[HDU 4336]Card Collection[状态压缩DP][概率DP][容斥原理]

题意:

小吃中有N种卡片,每种卡片 i 出现的概率为 pi ,一袋小吃有可能没有卡片,但最多有一张.问集齐所有卡片需要购买小吃的袋数期望.

思路:

1.用状压dp,dp[ s ]表示在s状态时,集齐所需要的袋数期望.

s = 11111表示N = 5时集齐的状态,此时dp[ s ] = 0;

注意求期望的题,对于dp的定义一般都是从终态转移到初态,也就是反着求.

因为"期望"是

确定事件的结果 * 该事件发生的概率 = 平均来看尝试一次可以得到的结果,即期望

若是在s1状态得到一张卡片转移到了s2,那么s2是一个确定的状态,而在s1时则有多种可能性.由此可以理解反着求的合理性.

终态是初态的"去向",确是期望的"来源".

//281MS	8480K
#include
using namespace std;
const int MAXN=22;
double p[MAXN];
double dp[1<=0;i--)//遍历所有方案
        {
            double x=0,sum=1;///肯定要拿自己那一张卡片
            for(int j=0;j 
 
//250MS  8480K
#include
using namespace std;
const int MAXN = 22;
double p[MAXN],dp[1<=0;i--)
        {
            double sump = 0,sum = 1;
            for(int j=0;j