传送门
期望dp简单题啊。
不过感觉题意不太对。
手过了一遍样例发现如果有捷径必须走。
这样的话就简单了啊。
设f[i]" role="presentation" style="position: relative;">f[i]f[i]表示从第i个格子出发到第n个格子的期望步数。
显然就可以从f[i+1]~f[i+6]转移过来了，注意如果f下标超过n期望步数都是0。
代码：
#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n,m,jump[N];
double f[N];
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int main(){
while(scanf("%d%d",&n,&m)){
if(!n&&!m)break;
memset(jump,0,sizeof(jump));
for(int i=1;i<=m;++i){int u=read(),v=read();jump[u]=v;}
f[n]=0;
for(int i=n-1;~i;--i){
f[i]=0;
if(jump[i]){f[i]=f[jump[i]];continue;}
for(int j=1;j<=6;++j){
int k=min(i+j,n);
f[i]+=f[k];
}
f[i]=f[i]/6.0+1;
}
printf("%.4lf\n",f[0]);
}
return 0;
}