题意

题目链接

给你一个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;
}