本文共 1653 字，大约阅读时间需要 5 分钟。

题目来源：

Description

玩家参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：

以 0 分开始，在得分少于 K 分时抽取数字。 抽取时，从 [1, W] 的范围中随机获得一个整数作为分数进行累计。 每次抽取都是独立的，其结果具有相同的概率。

当获得不少于 K 分时，就停止抽取数字。 求解分数不超过 N 的概率是多少？

Input

输入仅有一行，包括三个整数 N，K，W ( 0 <= K <= N <= 1000, 1 <= W <= 10000 ) 。

Output

输出一个浮点数，请保留 5 位小数，表示分数不超过 N 的概率。

Sample Input

6 1 10

Sample Output

0.60000

Note

如果答案与正确答案的误差不超过 10-5，则该答案将被视为正确答案通过。

解题思路

设f[i]表示得到 i 点分数的概率。那么f[0]=1;

• l=max(0,i-w)到r=min(i-1,k-1)中获取[l,r]区间。

只有[l,r]点分数这个区间才能够通过一次抽取获得i点分数。

最终的答案就是f[k]+f[k+1]…+f[n];

当然，为了方便我们可以使用一个数组d来存放前缀和，方便运算。

AC代码1：

#include 
   
    using namespace std;#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define endl '\n'const int MAXN = 1e4+5;double f[MAXN],d[MAXN];int main(){
       int n,k,w;    scanf("%d%d%d",&n,&k,&w);    if(k==0 || k+w<=n)    {
           printf("%.5f\n",1);        return 0;    }    f[0]=1;    d[0]=1;    for(int i=1;i<=n;i++)    {
           int l=max(0,i-w);        int r=min(i-1,k-1);        if(l==0) f[i]=d[r]/w;        else f[i]=(d[r]-d[l-1])/w;        d[i]=d[i-1]+f[i];    }    printf("%.5f\n",d[n]-d[k-1]);    return 0;}
   

AC代码2：

#include 
   
    using namespace std;#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define endl '\n'const int MAXN = 1e4+5;double dp[MAXN];int main(){
       int n,k,w;    scanf("%d%d%d",&n,&k,&w);    if(k==0 || k+w<=n)    {
           printf("%.5f\n",1);        return 0;    }    dp[0]=1;    double sum=1.0,ans=0.0;    for(int i=1;i<=n;i++)    {
           dp[i]=sum/w;        if (i>=w) sum-=dp[i-w];        if(i
   

转载地址：http://isyof.baihongyu.com/