首页 > 代码库 > hdu 4405 Aeroplane chess (概率dp)
hdu 4405 Aeroplane chess (概率dp)
/* 题目大意: 问从0到n所花费时间平均时间。每次有投骰子,投到几就走几步。当然了,还有近道。 题目分析: 假设现在在i,那么接下来有六种可能的走法,分别是: i到i+1,在由i+1到结束 i到i+2,在由i+2到结束 i到i+3,在由i+3到结束 i到i+4,在由i+4到结束 i到i+5,在由i+5到结束 i到i+6,在由i+6到结束 其中每一个可能的走法发生的概率为n为1/6。那么不妨定义dp(i),表示从i走到结束的期望。 那么有下面的等式: dp(i-1) = sum((dp((i-1)+j)+1)*p) 其中j ∈[0,6]。 当(i-1)+j >= n时,只需要时间1就可以结束。 当有近道(i,j)时,可以直接跳过去。dp(i)=dp(j)。 */ # include <stdio.h> # include <algorithm> # include <string.h> # include <iostream> using namespace std; int n; double dp[100010]; int h[100010]; void slove() { memset(dp,0,sizeof(dp)); for(int i=n; i>=1; i--) { double p=1.0/6.0;//骰子概率 for(int j=1; j<=6; j++) { int id=h[i-1]; if(id!=-1)//直接过来,不用掷骰子 dp[i-1]=dp[id]; else { if((i-1)+j>=n) dp[i-1]+=p; else dp[i-1]+=(dp[(i-1)+j]+1)*p; } } } } int main() { int m,a,b; while(~scanf("%d%d",&n,&m),n+m) { memset(h,-1,sizeof(h)); while(m--) { scanf("%d%d",&a,&b); h[a]=b; } slove(); printf("%.4lf\n",dp[0]); } return 0; }
hdu 4405 Aeroplane chess (概率dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。