算法提高 概率计算 （概率dp）

缺乏、安全感 2022-09-28 15:20 311阅读 0赞

问题描述

　　生成n个∈[a,b]的随机整数，输出它们的和为x的概率。

输入格式

　　一行输入四个整数依次为n，a，b，x，用空格分隔。

输出格式

　　输出一行包含一个小数位和为x的概率，小数点后保留四位小数

样例输入

2 1 3 4

样例输出

0.3333

数据规模和约定

　　对于50%的数据，n≤5.
　　对于100%的数据，n≤100,b≤100.

题解：简单的概率dp。

设dp[ i ][ j ]表示抽i个数，和为j的概率。

那么状态转移方程为：

dp[ i ] [ j ] += dp[ i - 1 ][ j - k ]*1.0/(b-a+1). (j > k).

代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. double dp[110][11000];
  4. //dp[i][j]表示抽 i个数和为j的概率
  5. int main()
  6. {
  7.     int n,a,b,x;
  8.     cin>>n>>a>>b>>x;
  9.     for(int i=a;i<=b;i++){
  10.         dp[1][i]=1.0/(b-a+1);
  11.     }
  12.     for(int i=2;i<=n;i++){ 
  13.         for(int k=a;k<=b;k++){  //第i个数为 k 
  14.             for(int j=1;j<=x;j++){  //和为 j 
  16.                 if(j-k>0){
  17.                     dp[i][j] += dp[i-1][j-k]*1.0/(b-a+1);
  18.                 }
  19.             }
  20.         }
  21.     }
  22.     printf("%.4lf\n",dp[n][x]);
  23.     return 0;
  24. }

发表评论

表情：
评论列表 （有 0 条评论，311人围观）

还没有评论，来说两句吧...

相关阅读

    相关 hdu 4586 概率dp

    题意： 扔一个有n面的骰子，可能得到正面朝上的那个面上面的数字，有一些面比较特殊，扔到这些面上之后可能继续扔，问最终能等到的数字和的期望。 分析： 这道题

    灰太狼灰太狼/ 0 赞/ 304 阅读

    相关 poj2096 概率dp入门

    题意： 一个系统有s个子系统，一共会产生n中bug。某人一天可以发现一个bug，这个bug属于一个子系统，属于一个种类，每个bug属于某个子系统的概率是1/s,属于某个分类的

    我就是我我就是我/ 0 赞/ 321 阅读

    相关 算法-->概率

    概率算法执行的基本过程如下： 将问题转化为相应的几何图形S，S的面积很容易计算，问题的结果往往对应几何图形中某一部分S1的面积。 然后向2几何图形中随机撒点

    傷城~傷城~/ 0 赞/ 288 阅读

    相关 CH3803 扑克牌（概率dp）

    题意：Rainbow把一副扑克牌(54张)随机洗开，倒扣着放成一摞。然后Admin从上往下依次翻开每张牌，每翻开一张黑桃、红桃、梅花或者方块，就把它放到对应花色的堆里去。 R

    迷南。迷南。/ 0 赞/ 457 阅读