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