D T4 飞行棋

题面

https://ac.nowcoder.com/acm/contest/7612/D

思路

数学期望题。

维护一个 数组， 代表从 到 的期望回合数。

通过列多元方程组可以得到 时 。 (这点数学基本功要有吧······)

然后就是一个递推的过程，要注意抛出 时即 到 时无需计算回合数，剩下的均要一个回合。

细节看代码注释

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>

using std::cin;using std::cout;using std::cerr;using std::endl;

#define rep(i,a,b) for(int i = a;i <= b;++i)
#define per(i,a,b) for(int i = a;i >= b;--i)

const int mmax = 1e5;

int T,n;
double d,dp[mmax + 10],sum[mmax + 10];

int main(){

    std::ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>T;

    while(T--){
        cin>>n>>d;
        int t = d;

        rep(i,1,t - 1){
            dp[i] = t - 1;
            sum[i] = sum[i - 1] + dp[i]; //前缀和维护，降低复杂度
        }

        dp[t] = dp[t - 1]  + 1 / d;
        sum[t] = sum[t - 1] + dp[t];

        rep(i,d + 1,n){
            dp[i] = (sum[i - 1] - sum[i - t] + d - 1) / d + dp[i - t] / t;
            //抛出的k的概率为 1 / d，
            //k < d 时到达终点的期望贡献为(1 + dp[i - k]) / d。
            //k = d 时到达终点的期望贡献为dp[i - k]。
            sum[i] = sum[i - 1] + dp[i];
        }

        printf("%.2f\n",dp[n]);    
    }

    return 0;
}