【HDOJ】【4405】Aeroplane chess飞行棋

概率DP/数学期望

　　kuangbin总结中的第4题

　　啊还是求期望嘛……（话说Aeroplane chess这个翻译怎么有种chinglish的赶脚……）

　　好像有点感觉了……

　　首先不考虑直飞的情况：

　　　　f[i]表示从第 i 格到end的期望掷骰子次数，那明显就是从f[i+1]~f[i+6]各1/6的概率（系数）转移过来啦~

　　那直飞呢？

　　　　so easy，f[i]=f[fly[i]]即可，其中fly[i]表示从第 i 格飞到的格子。当然直飞就不用再考虑1/6的掷骰子情况了……

　　从n-1往0逆推即可

P.S.多组数据记得清空数组哦~不要偷懒……那样容易出错的……

 1 //HDOJ 4405
 2 #include<cmath>
 3 #include<vector>
 4 #include<cstdio>
 5 #include<cstring>
 6 #include<cstdlib>
 7 #include<iostream>
 8 #include<algorithm>
 9 #define rep(i,n) for(int i=0;i<n;++i)
10 #define F(i,j,n) for(int i=j;i<=n;++i)
11 #define D(i,j,n) for(int i=j;i>=n;--i)
12 #define pb push_back
13 using namespace std;
14 int getint(){
15     int v=0,sign=1; char ch=getchar();
16     while(!isdigit(ch)) {if(ch=='-') sign=-1; ch=getchar();}
17     while(isdigit(ch))  {v=v*10+ch-'0'; ch=getchar();}
18     return v*sign;
19 }
20 const int N=1e5+10,INF=~0u>>2;
21 /*******************template********************/
22 const double p0=1.0/6;
23 double f[N];
24 int fly[N];
25 
26 int main(){
27 //    freopen("input.txt","r",stdin);
28     int n,m,x,y;
29     while(scanf("%d%d",&n,&m)!=EOF && n){
30         memset(fly,0,sizeof fly);
31         memset(f,0,sizeof f);
32         F(i,0,n+6) fly[i]=0;
33         F(i,1,m){
34             x=getint(); y=getint();
35             fly[x]=y;
36         }
37         D(i,n-1,0){
38             f[i]=1;
39             if (fly[i]) f[i]=f[fly[i]];
40             else F(j,1,6) f[i]+=p0*f[i+j];
41         }
42         printf("%.4lf
",f[0]);
43     }
44     return 0;
45 }

View Code