[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<cstdio>
using namespace std;
const int MAXN=22;
double p[MAXN];
double dp[1<<MAXN];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        double tt=0;
        for(int i=0;i<n;i++)
        {
            scanf("%lf",&p[i]);
            tt+=p[i];
        }
        tt=1-tt;//tt就表示沒有卡片的概率了
        dp[(1<<n)-1]=0;//全部收集到了就不需要再買了.求期望一般都是反著推.
        for(int i=(1<<n)-2;i>=0;i--)//遍歷所有方案
        {
            double x=0,sum=1;///肯定要拿自己那一張卡片
            for(int j=0;j<n;j++)
            {
                if((i&(1<<j)))x+=p[j];///如果此種卡片在i中已經存在,累加其概率
                else sum+=p[j]*dp[i|(1<<j)];///若不存在,說明可以由此種情況轉化而來
///dp[i|(1<<j)]是"確定事件",p[j]是該確定事件發生的概率,相乘則表示期望.
            }
            dp[i]=sum/(1-tt-x);
        }
        printf("%.5lf\n",dp[0]);

    }
    return 0;
}

//250MS  8480K
#include<cstdio>
using namespace std;
const int MAXN = 22;
double p[MAXN],dp[1<<MAXN];
int main()
{
    int N,m;
    while(scanf("%d",&N)==1)
    {
        for(int i=0;i<N;i++)
            scanf("%lf",p+i);
        m = 1 << N ;
        dp[m-1] = 0;
        for(int i=m-2;i>=0;i--)
        {
            double sump = 0,sum = 1;
            for(int j=0;j<N;j++)
            {
                if(!(i & (1<<j)))//位運算寫成了邏輯與...手殘
                {
                    sump += p[j];//有用的概率
                    sum += p[j]*dp[i|(1<<j)];
                }
            }
            dp[i] = sum / sump;
        }
        printf("%.5lf\n",dp[0]);///雖然樣例中輸出是保留了3位,但是題中描述是誤差1e-4的...所以...
    }
}