2016级算法第五次上机-D.AlvinZH的学霸养成记III
850 AlvinZH的学霸养成记III
思路
难题。概率DP。
第一种思考方式:直接DP
dp[i]:从已经有i个学霸到所有人变成学霸的期望。
那么答案为dp[1],需要从后往前逆推。对于某一天,有可能会增加一个学霸or不增加。
①增加:\((dp[i+1] + 1) * P\)
②不增加:\((dp[i] + 1) * (1-P)\)
其中,\(P = i * (n - i) * p / (C(n,2))\),C(n,2) = (n - 1) * n / 2。其含义是:n个人中选出一非学霸一学霸的方法数/n个人中选出两人方法数。
状态转移方程:\(dp[i] = (dp[i + 1] + 1) * P + (dp[i] + 1) * (1 - P)\)。移项化简后可得: \(dp[i] = dp[i + 1] + 1 / P\) 。
其实可能正着想更简单,令dp[i]表示达到班内有i个学霸的期望天数。则有dp[1] = 0。相同的分析分发,最后依然可以得到 \(dp2[i] = dp[i-1] + 1/P\) 。最后答案为dp[n]。
优化一下,完全不需要这个dp数组,使用一个变量累加即可得到答案。
第二种思考方式:期望叠加
每天至多有一个人转化为学霸,考虑第i个人转化为学霸的期望天数D[i],那么所有人转化为学霸的期望天数 \(ans=D[1]+D[2]+…+D[n-1]\)。
设第i个人转化为学霸的概率为p[i],则第i个人转化为学霸服从几何分布。
几何分布:在n次伯努利试验中,试验k次才得到第一次成功的机率。详细地说,是:前k-1次皆失败,第k次成功的概率。
期望\(EX=1*a+2*(1-a)*a+3*(1-a)^2*a+...\) ,错位相减求和即可得期望为 \(1/p[i]\)。
故 \(D[i]=1/p[i]\) ,而 \(p[i]=p*i*(n-i)/(n*(n-1)/2)\),所以 \(D[i]=n*(n-1)/(2*p*i*(n-i))\) ,那么我们就可以在O(n)的时间内得到ans值.
你可能已经发现,最后二者计算方法其实一模一样的,侧面证明答案正确。
分析
两种方法时间复杂度都为O(n)。
需要注意的问题是乘法溢出问题,在计算 \(n*(n-1) / (2*p*i*(n-i))\) 的过程中,有两个地方会溢出,一个是n(n-1),你可以通过(double)n(n-1)防止溢出,注意(double)(n(n-1))没有效果;第二个溢出是2i(n-i)p,你可以把p放前面先计算或者把i强制转换为浮点数防止溢出。
参考资料:有关概率和期望问题的研究
参考代码一
//
// Created by AlvinZH on 2017/9/15.
// Copyright (c) AlvinZH. All rights reserved.
//
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define MaxSize 100005
double dp[MaxSize];//dp[i]表示学霸数量为i时,到达目标的期望
int main()
{
int T, n;
double p, ans1, ans2, p1;
scanf("%d", &T);
while (T--)
{
scanf("%d%lf", &n, &p);
dp[n] = 0;
for (int i = n-1; i > 0; i--)
{
ans1 = (double)i * (n-i);//选出一非学霸和一学霸
ans2 = (double)n * (n-1) / 2;//从n个人中选两个人
p1 = ans1 / ans2 * p;
dp[i] = dp[i+1] + 1.0/p1;
}
printf("%.3lf\n",dp[1]);
}
return 0;
}
参考代码二
//
// Created by AlvinZH on 2017/9/15.
// Copyright (c) AlvinZH. All rights reserved.
//
#include<cstdio>
int main()
{
int T, n;
double p, ans;
scanf("%d", &T);
while (T--)
{
scanf("%d %lf", &n, &p);
ans = 0.0;
for(int i = 1; i < n; i++)
ans += 1.0 * n* (n-1) / (2 * p * i * (n-i));
printf("%.3lf\n", ans);
}
return 0;
}
最新文章
- 【手记】F5调试报";由于缺少调试目标xxx无法开始调试xxx设置OutputPath和AssemblyName";
- 调用JavaScript
- cmd命令查看局域网内计算机信息
- nginx的特点
- list,tuple,dict,字符串常用知识总结
- javascript正則表達式 &;quot;\b&;quot;问题
- 1.cocos2dx它Menu(CCMenuItemFont,CCMenuItemImage,CCMenuItemLabel,CCMenuItemSprite,CCMenuItemToggle)
- <;我的外骨骼,诺基>;后的访谈
- Centos 搭建LAMP环境
- 从给数组中的对象去重看Javascript中的reduce()
- [Swift]LeetCode849. 到最近的人的最大距离 | Maximize Distance to Closest Person
- JS获取字符串实际长度(包含汉字)的简单方法
- C++读写图片数据转成Base64格式的一种方法
- [HDU6146]Pok&#233;mon GO
- CloudSim源代码学习——虚拟机(VM)
- 使用html5获取当前手机的经纬度,并接入百度地图API,查询出当前位置
- centos7 安装zookeeper3.4.8集群
- mybatis BigDecimal Double Long 的坑爹事
- 20170831工作日记--自定义View学习
- NET Core中使用Angular2的Token base身份认证
热门文章
- [C++] Variable storage space
- code1006 等差数列
- Linux ls命令详解-乾颐堂CCIE
- Use formatter to format your JAVA code
- Spring.net 容器注入是替换(后处理器appConfigPropertyHolder)
- AJAX和DHTML
- 【转】ConcurrentMap 分析和思考
- 从零开始学习前端JAVASCRIPT — 11、JavaScript运动模型及轮播图效果、放大镜效果、自适应瀑布流
- C# SendKeys用法
- Statement 接口的应用(存在sql语句的注入风险)