題意：

買零食湊卡片的游戲，浪費錢。

給出每包糧食含有某一張卡片的概率，當然也可能什么也沒有。

問湊齊一套卡片的買的零食的數量的期望。

思路：

求期望，那么倒著dp。

因為n只有20，所以考慮用狀態壓縮來表示當前擁有的卡片的情況。

dp[sta]表示當前擁有卡片為sta時還需要買多少包零食，顯然dp[(1<<n)-1] = 0。

dp[x] =?Σdp[x|(1<<j)] * p[j]，因為當前可能有些卡片已經有了，所以dp[x] =?Σdp[x|(1<<j)] * p[j] +?Σdp[x] * p[k]，j為x表示中為0的點；

整理得到dp[x] = (Σdp[x|(1<<j)] * p[j]) / (Σp[j])，然后倒著dp即可。

代碼：

1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 using namespace std; 5 const int N = 21; 6 double dp[1<<N]; 7 double p[N]; 8 int main() 9 { 10 int n; 11 while (scanf("%d",&n) != EOF) 12 { 13 for (int i = 0;i < n;i++) scanf("%lf",&p[i]); 14 dp[(1<<n)-1] = 0; 15 for (int i = (1 << n) - 2;i >= 0;i--) 16 { 17 double tmp = 0; 18 for (int j = 0;j < n;j++) if (!(i&(1<<j))) tmp += p[j]; 19 double tt =0; 20 for (int j = 0;j < n;j++) 21 { 22 if (!(i&(1<<j))) 23 { 24 tt += dp[i|(1<<j)] * p[j]; 25 } 26 } 27 dp[i] = (tt + 1) / tmp; 28 } 29 printf("%.5f\n",dp[0]); 30 } 31 return 0; 32 }

?

轉載于:https://www.cnblogs.com/kickit/p/9013357.html

總結

以上是生活随笔為你收集整理的hdu 4336 Card Collector的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。