【题解】D-飞行棋(7612. 2020牛客NOIP赛前集训营-普及组(第五场))
T4 飞行棋
https://ac.nowcoder.com/acm/contest/7612/D
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; }