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=;i<n;i++)

     {

         cin>>p[i];

     }

 }

 void solve()

 {

     memset(dp,,sizeof(dp));

     for(int state=(<<n)-;state>=;state--)

     {

         double tot=;

         for(int i=;i<n;i++)

         {

             if(!((state>>i)&))

             {

                 dp[state]+=dp[state|(<<i)]*p[i];

                 tot+=p[i];

             }

         }

         dp[state]=(dp[state]+1.0)/tot;

     }

 }

 void print()

 {

     printf("%.9f\n",dp[]);

 }

 int main()

 {

     while(cin>>n)

     {

         read();

         solve();

         print();

     }

 }

巴特西

HDU 4336 Card Collector：状压 + 期望dp

最新文章

热门文章