题意
题目链接
给你一个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次即可，由于要用到区间和，用前缀和预处理一下即可，代码实现简单。
代码
代码语言：javascript复制#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("%.8lfn", t);
return 0;
}
