问题叙述性说明 生成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]); }版权声明：本文博主原创文章。博客，未经同意不得转载。
转载于:https://www.cnblogs.com/bhlsheji/p/4908700.html
相关资源：数据结构—成绩单生成器