题意：
总共有n+1个格子：0-n
初始情况下在 0号格子 每次通过掷骰子确定前进的格子数
此外 还有一些传送门可以瞬间从 u 点传送到 v 点（必须被传送）
求走到（或超过）n点总共需要掷多少次骰子
分析：
太弱 只想到了n^2的 dp方程 可惜n是100000...纠结半天又看了大牛的题解
用 dp[i]记录 走到第 i 个点时的期望 p[i]记录第 i 个点的概率。。、
这个概率记录的感觉比较神奇 ，我先开始想到的n^2是记录用 i 步 走到 j 点的概率
题解的这个概率应该是？？平均后的？？？f反正就是走到这个点了的概率直接把步数省去了 dp方程就少了一维
dp[i]=次数 * p 那么 如果对于 i+j 点 dp[i+j]= （次数+1）*p*1/6 = ( dp[i]+p[i] ) / 6;
就可以写出转移方程了
同时在维护一个next数组记录 传送门 如果next[i]!=i 则证明不可能停在第 i 点 因此就不通过此点进行转移 直接continue，并把 i 的信息保存在next[i]中
统计答案的时候注意要统计 n到 n+5的和
ac代码：
#include <iostream> #include <stdio.h> #include<string.h> #include<algorithm> #include<string> #include<ctype.h> using namespace std; #define MAXN 10000 int n,m; int next[100010]; double dp[100010]; double p[100010]; void ini() { memset(dp,0,sizeof(dp)); memset(p,0,sizeof(p)); for(int i=0;i<=100000;i++) { next[i]=i; } int u,v; for(int i=0;i<m;i++) { scanf("%d%d",&u,&v); next[u]=v; } } void solve() { dp[0]=0; p[0]=1; for(int i=0;i<n;i++) { if(next[i]!=i) { p[next[i]]+=p[i]; dp[next[i]]+=dp[i]; p[i]=0; continue; } for(int j=1;j<=6;j++) { p[i+j]+=p[i]*1.0/6.0; dp[i+j]+=(dp[i]+p[i])*1.0/6.0; } } double ans=0; for(int i=n;i<n+6;i++) { ans+=dp[i]; } printf("%.4f\n",ans); } int main() { while(scanf("%d%d",&n,&m),m+n) { ini(); solve(); } return 0; }
原文：http://www.cnblogs.com/oneshot/p/4001058.html