题意
玩线性飞行棋，一共有n个格子，每一次扔骰子，扔几点走几格，如果踩到了跳跃格，就跳过去，而且可以连续跳跃，走到或冲过终点游戏就胜利。问你扔多少次骰子之后游戏胜利（求期望）。
思路
很直接的概率dp题，加上了跳跃，不过因为我们的方向始终如一，所以没有成环的悲剧发生，可以很轻松的解出来。
我们设dp[i]表示位于第i格时，完成游戏需要的扔骰子数目,那么我们有：
![dp[i]=\sum_{k=1}^{6}(\frac{1}{6}dp[i+k])+1](https://haha.school/wp-content/ql-cache/quicklatex.com-82e85b13a5caab25ea141d5293cec0f7_l3.png "Rendered by QuickLaTeX.com")
对于a to b的跳跃关系，我们又有：
![dp[a]=dp[b]](https://haha.school/wp-content/ql-cache/quicklatex.com-3f127d83c3d9edca742fece887071f6d_l3.png "Rendered by QuickLaTeX.com")
这样dp方程就推好了。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> using namespace std; int fly[100010]; double dp[100010]; int flyme(int i){ if (fly[i]) { return fly[i] = flyme(fly[i]); }else{ return i; } } int main(){ int n = 0,m = 0; while (scanf(" %d %d",&n,&m)) { if (!(n+m)) { break; } memset(dp, 0, sizeof(dp)); memset(fly, 0, sizeof(fly)); for (int i = 1; i <= m; i++) { int from = 0,to = 0; scanf(" %d %d",&from,&to); fly[from] = to; } for (int i = n-1; i >= 0;i--) { for (int j = 1; j <= 6; j++) { dp[i] += dp[flyme(i+j)]/6; } dp[i]++; } printf("%.4lf\n",dp[0]); } return 0; } |
