原题 一道概率dp题，这里尤为要注意的是，必须从后往前dp。1因为：i到节点i+1i+6每个概率都是1/6，但是节点i-6i-1到i点每个概率却不是1/6。 2因为：并且比如从a到b有近道，如果从前往后，那么到b的概率和a就一样了，明显这是不可能的。但是，从b到a的话，那一定是dp[a]=dp[b]，因为有近道超近道。 因为是从后往前，所以有近道超近道。
#include<bits/stdc++.h> using namespace std; const int MX=1e5+9; int n,m,len[MX],a,b; double dp[MX]; int main() { freopen("input.txt","r",stdin); while( scanf("%d %d",&n,&m) && ( n||m ) ){ memset(len,0,sizeof(len)); memset(dp,0,sizeof(dp)); for( int i=1 ; i<=m ; i++ ){ scanf("%d %d",&a,&b); len[a]=b; } for( int i=n-1 ; i>=0 ; i-- ){ if( len[i]!=0 ) dp[i]=dp[len[i]]; // 有近道超近道 else{ for( int j=1 ; j<=6 ; j++ ) dp[i]+=(dp[i+j]/6.0); // i到节点i+1~i+6每个概率都是1/6 dp[i]++; } } printf("%.04lf\n",dp[0]); } return 0; }