题目链接:Click here~~
题意:
有一排 n+1 个格子,编号 0~n ,有些格子可以坐飞机向前飞,飞到某个指定的格子。
然后从0出发,每次掷个骰子(1~6点),然后走对应的步数,若走到有飞机的地方,则飞过去。否则,掷骰子。
问走到编号为n的格子或者走到它后面的关于掷骰子次数的期望是多少。
解题思路:
设 P[i] 表示到达格子 i 的概率,E[i] 表示到达格子 i 掷骰子次数的期望。
首先,对于到达格子 i 这一事件,只有两种可能:坐飞机过来的 or 掷骰子过来的。
若它是从格子 k 坐飞机过来的,则 P[i]1 = P[k]。
若它是从格子 k 掷骰子过来的,则 P[i]2 = P[k] * 1/6 ( i-6 <= k <= i-1)。
即 P[i] 等于上述两种情况的概率和。
设掷骰子次数为 t ,则 E[i] = sum{t * P[i] * p(i,t)}。(p(i,t) 表示到达格子 i 的条件下掷骰子次数为 t 的概率)
若它是从格子 k 坐飞机过来的,则 p(i,t) = p(k,t) ,又 P[i]1 = P[k],从而 E[i]1 = E[k]。
若它是从格子 k 掷骰子过来的,则 p(i,t) = p(k,t-1),又 P[i]2 = P[k] * 1/6,
则 E[i] = 1/6 * sum{(t-1) * P[k] * p(k,t-1)} + 1/6 * P[k] * sum{ p(k,t-1) } ,从而E[i]2 = 1/6 * ( E[k] + P[k] )。
同理 E[i] 等于上述两种情况的期望和。
如此,便可从前向后递推求解。
#include <stdio.h>
#include <string.h>
#define N 100010
const double p = 1.0/6;
struct TT
{
double E,P;
int next;
}a[N];
int main()
{
int n,m,x,y;
while(scanf("%d%d",&n,&m),n+m)
{
memset(a,0,sizeof(a));
while(m--)
{
scanf("%d%d",&x,&y);
a[x].next = y;
}
a[0].E = 0 , a[0].P = 1;
for(int i=0;i<n;i++)
{
if(a[i].next)
{
a[ a[i].next ].E += a[i].E;
a[ a[i].next ].P += a[i].P;
}
else
for(int j=1;j<=6;j++)
{
a[i+j].E += p * (a[i].E + a[i].P);
a[i+j].P += p * a[i].P;
}
}
double ans = 0;
for(int i=0;i<=5;i++)
ans += a[n+i].E;
printf("%.4f\n",ans);
}
return 0;
}
分享到:
相关推荐
HDU的一题........HDU DP动态规
杭电oj4405,一道简单的概率dp题目
动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman...1957年出版了他的名著Dynamic Programming,这是该领域的第一本著作。
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
HDU上DP大集合,里面包括题,题解,代码,对DP入门者很实用,对DP老手也是有很大的提高
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。
压缩包包含十份报告,已经通过验收,实验内容:交换机、生成树、静态路由、NAT等完全根据教材实验要求
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
算法-确定比赛名次(HDU-1285).rar
华为HLR相关资料,介绍了HLR中的HDU数据库单元原理
动态规划DP题解 POJ HDU部分动态规划DP题解
hdu 1005.比较简单的一道题,有兴趣的可以看看。
HDU 1010-2500解题报告,ACMer可以借鉴一下
hdu2000-2014ac代码,虽然只有几道,但都是简单的
2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)
示例 1:示例 2:解答:大小写转换: n = n ^ 32转小写: n = n | 32转大写: n = n & -33const toLowerCase =
ACM入门的课件适合于那些想要学习的ACM,提高自己编程能力的。
hdu 期末考试复习资料 计算机网络 编译原理 计算机图形学 编译原理 信息安全与技术 数据库应用系统开发
从第 1 秒开始,每 一秒最 开始 时,每个数据服务器都会检查它是否收到了主服务器的回复信息(包括新发出信息的回复信息):如果还没收到任何回复信息,那么该服务器