Aeroplane chess
题目大意：从0~n有n+1个格子，一个人从0开始出发，每走一次掷色子，行走的距离由色子的点数决定（1到6），每种可能性均相等。问到达n这个格子的平均次数。
解题思路：由题意不难想到用dp[i]中的i表示所处的位置。首先如果我们从0开始推对于每个点有6种方式前进，再到一个新的点又会有6种方式前进，那么情况会越来越复杂。不妨使用逆推的方法，从n-1开始，对于它后面的6个点都只有1种方式到达。所以对于n-1点只需1次到达n。然后，以这样的方法向前推，例如n-2,把n-1当作终点…以此类推。
代码：
#include <bits/stdc++.h> using namespace std; double dp[100010]; int a[100010]; int main() { int n,m; while(scanf("%d%d",&n,&m)){ if(n==0&&m==0)break; memset(dp,0,sizeof(dp)); memset(a,0,sizeof(a)); for(int i=1;i<=m;i++){ int st,en; scanf("%d%d",&st,&en); a[st]=en; } for(int i=n-1;i>=0;i--){ if(!a[i]){ for(int j=1;j<=6;j++){ dp[i]+=dp[i+j]/6.0; } dp[i]++; }else{ dp[i]=dp[a[i]]; } } printf("%.4lf\n",dp[0]); } return 0; }