QUTOJ-1363 麻煩的轉盤（機率dp）

1362: 麻煩的轉盤

時間限制: 1 Sec   記憶體限制: 128 MB

送出: 130   解決: 35

題目描述

有一個轉盤，如下圖所示，問轉動n次轉盤，總和為m的機率是多少 

輸入

輸入n和m

(1<=n<=100 , 1<= m <= 600)

輸出

題目要求的機率值，結果保留4位小數

樣例輸入

1 13 4      

樣例輸出

0.25000.0469      

  機率dp，炒的題解，入門題，确實不難

連結here

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int main()
{
    double num[115][415] = {1.0};
    for(int i = 1;i <= 105;i++)
    {
        for(int j = 1;j <= 405;j++)
        {
            num[i][j] += 0.25*num[i-1][j-1];
            if(j >= 2)   num[i][j] += 0.25*num[i-1][j-2];
            if(j >= 3)   num[i][j] += 0.25*num[i-1][j-3];
            if(j >= 4)   num[i][j] += 0.25*num[i-1][j-4];
        }
    }
    int n,m;
    while(~scanf("%d%d",&n,&m))
        printf("%.4f\n",num[n][m]);
    return 0;
}