E - Throwing the Die
https://atcoder.jp/contests/abc266/tasks/abc266_e

自下而上DP,很有趣hhhhh

大概原理就是我们可以知道如果已经投了N次,那么结果的期望就是最后投出来的值(1-6),那么就可以反推上一层决策时的期望是下层之和除以6的结果。

因为要期望最大,所以显然下一层大于上一层期望的点会选择终止游戏(否则期望就会变低),而小于上层的点就会选择继续游戏以提高期望...

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
double dp[N][7];
int main(){
    int n;
    double ans = 3.5;
    cin>>n;
    for(int i = 1; i <= 6; i++) dp[n + 1][i] = i;
    for(int i = n; i > 0; i--){
        double sum = 0;
        for(int j = 1; j <= 6; j++){
            sum += dp[i + 1][j];
        }
        double avg = sum / 6;
        for(int j = 1; j <= 6; j++){
            dp[i][j] = max(double(j), avg);
            sum += dp[i][j];
        }
        ans = max(ans, avg);
    }
    cout<<ans;
    return 0;
}