首页 > 代码库 > hdu 4405 Aeroplane chess(概率DP)
hdu 4405 Aeroplane chess(概率DP)
题目链接:hdu 4405 Aeroplane chess
题意:
一个0到n的数轴上掷色子前进,中间有直达部分,问到终点需要掷色子的期望。
题解:
无环的期望DP,直接递推就行。
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 using namespace std; 4 5 const int N=1e5+7; 6 double dp[N]; 7 int n,m,vis[N]; 8 9 int main(){ 10 while(scanf("%d%d",&n,&m),n+m) 11 { 12 F(i,0,n)vis[i]=-1; 13 F(i,1,m) 14 { 15 int x,y; 16 scanf("%d%d",&x,&y); 17 vis[x]=y; 18 } 19 F(i,0,n+6)dp[i]=0; 20 for(int i=n-1;i>=0;i--) 21 { 22 if(vis[i]!=-1){dp[i]=dp[vis[i]];continue;} 23 F(j,1,6)dp[i]+=dp[i+j]/6; 24 dp[i]+=1; 25 } 26 printf("%.4f\n",dp[0]); 27 } 28 return 0; 29 }
hdu 4405 Aeroplane chess(概率DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。