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

一道简单的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
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 ;

}

};

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

转发分享

▲