【题解】D-飞行棋（7612. 2020牛客NOIP赛前集训营-普及组（第五场））

D-飞行棋

思路

设 为从 走到 的 步数。

• 当 时，
• 当 时， 期望为 。

来源：2020牛客NOIP赛前集训营-普及组（第五场）题解 【链接】

代码

#include<bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n, d;
        cin >> n >> d;
        if(d == 1) {
            cout << "1.00" << endl;
        }
        else if(n < d) {
            cout << fixed << setprecision(2) << d-1.00 << endl;
        }
        else {
            double f[100005], sum[100005];
            memset(f, 0x00, sizeof(f));
            memset(sum, 0x00, sizeof(sum));
            f[0] = sum[0] = 1;
            for(int i = 1 ; i < d, i <= n ; i++) {
                f[i] = d - 1.00;
                sum[i] = sum[i-1] + f[i];
            }
            for(int i = d ; i <= n ; i++) {
                    f[i]   = (sum[i-1] + f[i] - f[i-d-1])/d;
                    sum[i] = sum[i-1] + f[i] - f[i-d-1];
            }
            cout << fixed << setprecision(2) << f[n] << endl;
        }
    }
    return 0;
}