hihoCoder太閣最新面經算法競賽8 題目2 : Dice Possibility （機率DP）

題目2 : Dice Possibility

時間限制: 10000ms 單點時限: 1000ms 記憶體限制: 256MB

描述

What is possibility of rolling N dice and the sum of the numbers equals to M?

輸入

Two integers N and M. (1 ≤ N ≤ 100, 1 ≤ M ≤ 600)

輸出

Output the possibility in percentage with 2 decimal places.

樣例輸入

2 10      

樣例輸出

8.33      

題意:用N個骰子扔出總點數為M的機率是多少。

題解：機率DP。dp[i][j]表示扔 i 個骰子，點數為 j 的機率。

AC代碼：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int N,M;
	double dp[101][601] = {0};
	cin >>N>>M;
	for (int i = 1; i <= 6; i++)
	{
    	dp[1][i]=(1.0/6);
	}
	
	for (int i = 2; i <= N; i++)
	{
    	for (int j = i; j <=M; j++)
   	  {
        if(j-i<6)
		{
            for(int k = i-1;k<j;k++)
			{
                dp[i][j] += dp[i-1][k]/6;
                
            }
        }
        else
		{
            for(int k =j-6;k<j;k++)
			{
                dp[i][j] += dp[i-1][k]/6;              
            }
        } 
      }
	}
	printf("%.2lf\n",dp[N][M]*100);
	return 0;
}