hdu 4336 Card Collector (概率dp)

题目大意：

收集卡片，问收集齐n张卡片需要买多少包方便面的期望- -虽然不是方便面。

解题思路：

用1表示该位的卡片已经有，0表示没有。

dp[s] 表示拥有了s状态下1的卡片，还要买多少包才能凑齐n张卡片的期望。

所以 ，当你及其了所有的卡片。即 dp[(1<

下面再来分析状态转移。

假设我们要收集齐 6 张，可是现在我们收集齐了五张。 那么你要中第六张。

就是第六包要中1 或2 或3 ...或6...

所以要枚举所有 五包的情况，然后因为任一种情况都是互不影响的，所以是相加。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; double p[25]; double dp[1<<21]; int main() { int n; while(scanf("%d",&n)!=EOF) { for(int i=0;i
      
       =0;s--) { dp[s]=1.0; double tmp=0; for(int j=0;j