题目1 : 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的组合方式数量。
状态：d[i][j]表示仍i次骰子的和为j的组合方式数量。
状态转移方程：d[i][j] = d[i - 1][j - v] + d[i][j]。v表示骰子的数1-6。

根据上面的方式则求出：p = d[N][M] / 6^N。
N次幂数值太大，做题尽量避免指数。

状态：d[i][j]表示仍i次骰子的和为j的概率。
状态转移方程：d[i][j] = d[i][j] + d[i - 1][j - v] * (1/6)。v表示骰子的数1-6，乘上最后一次扔v的概率1/6，注意要把最后的6种情况加起来，因为最后一步有6种可能都能加起来得到M，几种概率是并行的，所以求和。

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <string>
#include <string.h>
#include <iomanip>
using namespace std;

int main()
{
    int N, M;
    cin >> N >> M;
    double d[105][605];
    memset(d, 0, sizeof(d));
    for(int i = 1; i <= 6; i++) d[1][i] = 1.0/6;
    for(int i = 2; i <= N; i++) {
        for(int j = i; j <= N * 6; j++) {
            for(int v = 1; v <= 6 && j - v >= i - 1; v++) {
                d[i][j] += d[i - 1][j - v] * (1.0/6);
            }
        }
    }
    cout << fixed << setprecision(2) << d[N][M] * 100 << endl;
    return 0;
}