首页 > 代码库 > hdu 4405 Aeroplane chess

hdu 4405 Aeroplane chess

2024-07-15 03:57:04   215人阅读

题意：

hzz一开始在0位置，然后hzz掷骰子，骰子为i,就往前走i步，当hzz位置大于等于n的时候结束，求掷骰子次数的期望

有m个直达点 （x,y）,走到x时可以直接到y

求期望一般从后往前推

当 i不等于任何一个x时

dp[i]=seg(1/6*dp[i+k])+1

否则

dp[i]=dp[y]

 1 #include<iostream> 2 #include<string> 3 #include<cstdio> 4 #include<vector> 5 #include<queue> 6 #include<stack> 7 #include<algorithm> 8 #include<cstring> 9 #include<stdlib.h>10 using namespace std;11 #define pb push_back12 struct node{13     int x,y;14 }p[1010];15 int cmp(node a,node b){16     return a.x<b.x;17 }18 int main()19 {20     int n,m;21     while(cin>>n>>m,n+m){22         double dp[101010];23         memset(dp,0,sizeof(dp));24         for(int i=0;i<m;i++)25             scanf("%d%d",&p[i].x,&p[i].y);26         sort(p,p+m,cmp);27         int cnt=m-1;28         for(int i=n-1;i>=0;i--){29               dp[i]=1;30               if(cnt>=0&&i==p[cnt].x){31                dp[i]=dp[p[cnt].y];32                cnt--;33                continue;34               }35               for(int j=6;j>=1;j--)36                 dp[i]+=1.0/6*dp[i+j];37         }38         printf("%.4f\n",dp[0]);39     }40 }

 


联系
我们