hiho一下第174周《Dice Possibility》题目分析

1
0

比较容易的动态规划。
用f[i][j]表示掷了i枚骰子,点数之和是j的概率。
递推方程留给大家推导~

提示:考虑最后一枚骰子的点数

  • 我想问一下,我的表示方法是这样的,就是f[i][j]表示i枚骰子,点数之和是j的可能次数,比如f[2][3],表示2枚骰子,点数之和是3有2种可能,然后得到这样一个表之后,我再取出f[n]m]的值,除以pow(6,n),再乘上100,为什么最后才有60分?难道跟答案的精度有关?[

  • 注意f[i][j]应该开double型..开longlong会爆的

  • 添加评论
  • reply

2 answer(s)

0

class Solution { public: double Dice_Posibility1(int dice_num,int number){ if (dice_num<1 || number>dice_num*max_numpre || number < dice_num*min_numpre) return 0.0; int col = number + 1; int row = dice_num + 1;

    int* Posbility = new int[col*row];
    for (int i = 0; i < col*row; i++)
        Posbility[i] = 0;
    for (int i = col + min_numpre; i < col + max_numpre; i++)
        Posbility[i] = 1;
    for (int i = col * 2; i<col*row; i++){
        if (i%col>=i / col){
        int up_limit = (i%col + 1 - i / col)>6 ? 6 : (i%col + 1 - i / col);
        for (int k = 1; k <= up_limit; k++){
            Posbility[i] += Posbility[(i / col - 1)*col + i%col - k];


        }


    }





    }

    double res = (double)Posbility[col*row - 1];
    for (int i = 0; i < dice_num; i++)
        res /= 6.0;

    return res ;

}

};

0

一道简单的dp ,dp方程 : dp[i][j] += dp[i-1][j-t]*p ,i为当前投掷次数,j为总分,t为增量(因为增量最多为6不大,不需要结构维护)。

#include <cstdio>
using namespace std;

#define Fin(i,f,t) for(int i = f; i <= t; ++i)
const int N = 120;
const int M = 620;
const double p = 1.0/6;

double dp[N][M];

void Init(){
    Fin(i,1,6)
        dp[1][i] = p;
    Fin(i,2,100){
        Fin(t,1,6){
            Fin(j,(i-1)+1,6*(i-1)+6) if(j > t)
                dp[i][j] += dp[i-1][j-t]*p;
        }
    }
}
int main()
{
    Init();
    int n,m;
    while(~scanf("%d %d",&n,&m)){
        printf("%.2lf\n",100 * dp[n][m]);
    }
    return 0;
}
  • 乘以的p是什么含义?

  • 骰子每面1/6概率,是个定值

  • 请问一下这段循环是什么意思 ? Fin(j,(i-1)+1,6*(i-1)+6) if(j > t) dp[i][j] += dp[i-1][j-t]*p;

  • 这一步走完最少i分,最多6*i分。

  • 添加评论
  • reply

write answer 切换为英文 切换为中文


转发分享