[ABC266E] Throwing the Die 题解

· · 题解

解法

设 f(i) 为到第 i(1\le i\le n) 局游戏时最大分数的期望值；

很显然，第 i-1 轮游戏结束后，下一局游戏 1,2,3,4,5,6 的出现概率均等（记下一局的得分为 x），则易得下一局游戏的得分对答案有贡献的充要条件为 x>f(i)（否则上一局的分数更高，取上一局的分数）。

这样，我们就很容易推出：

f(i)=\sum\limits_{j=1}^6\frac{1}{6}\max\{f(i-1),j\}

实现

递推或递归实现即可。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int n; double c=0; cin>>n;
  for(int i=1;i<=n;i++){
    double c0=0;
    for(int j=1;j<=6;j++)c0+=max(c,1.0*j);
    c=c0/6;
  }
  cout<<fixed<<setprecision(9)<<c<<endl;
  return 0;
}