概率统计(DP)

问题叙述性说明

  生成n个月∈[a,b]随机整数。并且将它们输出到x概率。

输入格式

  输入线跟四个整数n。a,b,x,用空格分隔。

输出格式

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

例子输入

2 1 3 4

例子输出

0.3333

数据规模和约定

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

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

题解:

这是一道典型的全然背包,可是在做的过程中遇到了一些波折。

dp[i][j]:挑选i个数字后得到j的概率。

dp[i][j]=dp[i-1][z]*1/sum;

每一种情况都要再乘一个1/sum,而情况与情况之间是加和的关系。

(最開始想用得到X数/总数),后来发现到最后实在太大了。100^100.所以用dp直接表示概率更好一点,剩下的就是一个全然背包了。

代码实现:

#include <bits/stdc++.h>
#define MAX 110 using namespace std; double dp[MAX][MAX*MAX];
double sum;
int N,a,b,X; int main()
{
scanf("%d%d%d%d",&N,&a,&b,&X);
sum = b-a+1;
memset(dp,0,sizeof(dp));
for( int i = 0; i < N; i++ )
{
for( int j = a; j <= b; j++ )
{
if( i == 0 )
dp[i][j]=1/sum;
else
{
for( int z = 0; z <= X; z++ )
{
if( dp[i-1][z] != 0 )
dp[i][z+j]+=(dp[i-1][z]*1/sum);
}
}
}
}
printf("%.4lf\n",dp[N-1][X]);
}

版权声明:本文博主原创文章。博客,未经同意不得转载。

上一篇:我需要在电脑上安装C编译器


下一篇:C#生成高清缩略图