HDU 4336 Card Collector：期望dp + 状压

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

题意：

　　一共有n种卡片。每买一袋零食，有可能赠送一张卡片，也可能没有。

　　每一种卡片赠送的概率为p[i]，问你将n种卡片收集全，要买零食袋数的期望。

题解：

　　表示状态：

　　　　dp[state] = expectation

　　　　state表示哪些卡片已经有了

　　找出答案：

　　　　ans = dp[0]

　　　　什么都没有时的期望袋数

　　如何转移：

　　　　两种情况，要么得到了一张新的卡片，要么得到了一张已经有的卡片或者啥都没有。

　　　　　　dp[state] = ∑ (dp[state|(1<<i)]*p[i]) + dp[state]*(1 - ∑ p[i]) + 1

　　　　　　((state>>i)&1 == 0)

　　　　移项后：

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

　　边界条件：

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

　　　　已经集全了。

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define MAX_N 25

 #define MAX_S ((1<<20)+50)

 using namespace std;

 int n;

 double p[MAX_N];

 double dp[MAX_S];

 int main()

 {

     while(cin>>n)

     {

         for(int i=;i<n;i++) scanf("%lf",&p[i]);

         dp[(<<n)-]=;

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

         {

             double sum=;

             dp[state]=;

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

             {

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

                 {

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

                     sum+=p[i];

                 }

             }

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

         }

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

     }

 }

巴特西

HDU 4336 Card Collector：期望dp + 状压

最新文章

热门文章