Deceptive Dice(期望计算)

题意

题目链接

给你一个n个面的骰子,你最多可以投k次,你可以在任意一次停止投掷骰子,并将最后一次的结果作为你的得分,骰子每一面出现的概率均等,让你求最多投k次得分的期望为多少。

分析

我们以20面的骰子最多投3次为例:

只投掷一次: 每一面出现的概率都是$\frac{1}{20}$,再乘上每种情况的得分,可得:$\frac{1}{20} * \sum^{20}_{i= 1}{i} = 10.5$

最多投两次: 投一次的期望是10.5分,所以只有第一次得分低于10.5才进行第二次投掷,故分为投一次和投两次的情况,投一次的期望为:$\frac{1}{20} * \sum_{i=11}^{20}i$,投两次的期望可以看成在第一次投掷结果为1-10的前提下,再投一次,即第一次投掷结果为1-10的概率乘上只投掷一次的期望。综上,公式为:$\frac{1}{20} * \sum_{i=11}^{20}i+\frac{10}{20} * 10.5 = 13$

最多投三次: 投两次的期望为13,那么第一次如果投掷的结果为1-13,那么投掷两次肯定更优,故可以分为两种情况考虑:第一次投掷结果为14-20,那么只要投一次,期望为:$\frac{1}{20} * \sum_{i=14}^{20}i$;第一次结果为1-13,那么还需要继续投掷,可以看成在第一次投掷结果为1-13的基础上最多投掷两次的期望,即:$\frac{13}{20} * 13$

可以发现,每次的结果都是由上一步推得,可以得出一个递推关系,那么求n面骰子,投k次只要从1次一直推到k次即可,由于要用到区间和,用前缀和预处理一下即可,代码实现简单。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;

double s[110];
LL n, k;
int main() {
    scanf("%lld %lld", &n, &k);
    for (LL i = 1; i <= n; i++) {
        s[i] = s[i - 1] + i;
    }
    double t = s[n] / n;
    for (LL i = 2; i <= k; i++) {
        LL pos = (LL)t;  
        t = (s[n] - s[pos]) / n + (pos)*t / n;
    }
    printf("%.8lf\n", t);  
    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇