狀壓dp入門，HDU 4336 Card Collector：狀壓 + 期望dp

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=4336

題意：

　　有n種卡片(n <= 20)。

　　對于每一包方便面，里面有卡片i的概率為p[i]，可以沒有卡片。

　　問你集齊n種卡片所買方便面數量的期望。

?

題解：

　　狀態壓縮。

　　第i位表示手上有沒有卡片i。

?

　　表示狀態：

　　　　dp[state] = expectation

　　　　（卡片狀態為state時，要集齊卡片還要買的方便面數的期望）

?

　　找出答案：

　　　　ans = dp[0]

　　　　剛開始一張卡片都沒有。

?

　　如何轉移：

　　　　now: dp[state]

　　　　對于卡片i，如果手上已經有了i，則方便面里有i等價于面里什么都沒有。

　　　　所以子期望共兩種：

　　　　　　（1）拿到一張還沒有的卡片i。

　　　　　　（2）拿到垃圾2333。

　　　　dp[state] = sigma( dp[state|(1<<i)] * p[i] ) + dp[state] * P(useless) + 1

　　　　P(useless)為拿到垃圾的概率。

　　　　設tot = sigma(p[i])

　　　　P(useless) = 1 - tot

　　　　原式移項后：

　　　　　　dp[state] = ( sigma( dp[state|(1<<i)] * p[i] ) + 1 ) / tot

?

　　邊界條件：

　　　　dp[(1<<n)-1] = 0

　　　　已經集齊，不用再買。

?

AC Code:

// state expression:
// dp[state] = expectation
// state: state of present cards
//
// find the answer:
// ans = dp[0]
//
// transferring:
// now: dp[state]
// dp[state] = sigma( dp[state|(1<<i)] * p[i] ) + dp[state] * P(useless) + 1
// i: not been collected
// dp[state] = ( sigma( dp[state|(1<<i)] * p[i] ) + 1 ) / (1 - P(useless))
// dp[state] = ( sigma( dp[state|(1<<i)] * p[i] ) + 1 ) / tot
//
// boundary:
// dp[(1<<n)-1] = 0
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 25
#define MAX_S ((1<<20)+5)

using namespace std;

int n;
double p[MAX_N];
double dp[MAX_S];

void read()
{
    for(int i=0;i<n;i++)
    {
        cin>>p[i];
    }
}

void solve()
{
    memset(dp,0,sizeof(dp));
    for(int state=(1<<n)-2;state>=0;state--)
    {
        double tot=0;
        for(int i=0;i<n;i++)
        {
            if(!((state>>i)&1))
            {
                dp[state]+=dp[state|(1<<i)]*p[i];
                tot+=p[i];
            }
        }
        dp[state]=(dp[state]+1.0)/tot;
    }
}

void print()
{
    printf("%.9f\n",dp[0]);
}

int main()
{
    while(cin>>n)
    {
        read();
        solve();
        print();
    }
}

?