题意
飞行棋。有n+1格，开始时在0号格子，每一步都要扔一个dice（六个面，概率相同）哪一面朝上他就会向前走x+i步。当x+i大于等于N的时候，游戏结束。另外，地图上有m条航线。第i条航线可以直接从xi到yi。计算扔dice次数的期望。
分析
这个题有一个默认的条件，如果当前格子有航线可以选择，那么就一定选择航线而不是掷色子。
最简单的概率DP，状态的定义需要从后往前定义，因为航线的缘故只能从后往前转移。
定义f[i]为 从第i个格子到n个格子的期望次数是多少。
如果i格子有航线那么 f[i]=f[to] ,to是航线可以到达的格子。
如果i格子没有航线，那么f[i]=sum(1/6*f[i+k])+1,其中k是色子的六个面(1,2,3,4,5,6)。
code
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> using namespace std;
const int maxn=+;
int n,m;
int line[maxn];
double f[maxn];
int main(){
while(scanf("%d%d",&n,&m)!=EOF&&(n||m)){
memset(f,,sizeof(f));
memset(line,-,sizeof(line)); int x,y;
for(int i=;i<=m;i++){
scanf("%d%d",&x,&y);
line[x]=y;
}
for(int i=n-;i>=;i--){
if(line[i]!=-){
f[i]=f[line[i]];
}
else{
for(int j=;j<=;j++){
int to=min(n,i+j);
f[i]+=(f[to]+)*(double)/;
} }
}
/* for(int i=0;i<=n;i++){
printf("%d %.4f\n",i,f[i]);
}*/
printf("%.4f\n",f[]);
}
return ;
}