hdu 4405 概率dp

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 using namespace std;
 8 const int maxn=100005;
 9 int n,m,t;
10 int hash1[maxn];
11 double dp[maxn];
12 int main()
13 {
14     int i,j,k;
15     #ifndef ONLINE_JUDGE
16     freopen("1.in","r",stdin);
17     #endif
18     while(scanf("%d%d",&n,&m)!=EOF)
19     {
20         if(n==0&&m==0)  break;
21         int a,b;
22         memset(hash1,-1,sizeof(hash1));
23         for(i=0;i<m;i++)
24         {
25             scanf("%d%d",&a,&b);
26             hash1[a]=b;
27         }
28         memset(dp,0,sizeof(dp));
29         for(i=n-1;i>=0;i--)
30         {
31             if(hash1[i]!=-1) dp[i]=dp[hash1[i]];
32             else
33             {
34                 for(j=1;j<=6;j++)   dp[i]+=dp[i+j];
35                 dp[i]=dp[i]/6+1;
36             }
37         }
38         printf("%.4lf\n",dp[0]);
39     }
40 }