第一场多校,感觉自己都跳去看坑自己的题目里去了,很多自己可能会比较擅长一点的题目没看,然后写一下其中一道概率题的题解吧,感觉和自己前几天做的概率dp的思路是一样的。下面先来看题意:一个人有两个TC的账号,一开始两个账号rating都是0,然后每次它会选择里面rating较小的一个账号去打比赛,每次比赛有p的概率+1分,有1-p的概率-2分,当然如果本身是<=2分的也就还是回到0分。然后问最后其中一个账号到达20分时需要打多少次比赛。
先考虑一场比赛的情况,定义dp[k]为当前为k分,要达到20分时的期望回合数。(令q=1-p)
那么显然有 dp[0]=1+p*dp[1]+q*dp[0] 化简得 dp[0]=1/p+dp[1]
dp[1]=1+p*dp[2]+q*dp[0] 化简得 dp[0]=1/p+1/p^2+dp[2]
我们令 dp[0]=tk+dp[k] 那么tk就表示由0状态到达k状态所需的期望回合数。那么显然如果是要到达20分的话,答案就是t20
然后我们看 dp[k]=1+p*dp[k+1]+q*dp[k-2] 代入dp[0]=dp[k]+tk 就有
dp[0]=1/p+1/p*t[k]-(1-p)/p*t[k-2]+dp[k+1]
所以 t[k+1]=1/p+1/p*t[k]-(1-p)/p*t[k-2]
边界条件是 t[0]=0,t[1]=1/p,t[2]=1/p+1/p^2
知道这些就可以递推出所有需要的t[k]了。
现在我们来看如果有两个账号怎么破。首先我们必然是 (0,0)->(0,1)->(1,1)->(1,2)->(2,2)->(2,3)->(3,3)...
(0,0)->(0,1)需要的期望回合数是t[1]-t[0]. (0,1)->(1,1)需要的期望回合数是 t[1]-t[0]
(1,1)->(1,2)需要的期望回合数是t[2]-t[1]. (1,2)->(2,2)需要的期望回合数是 t[2]-t[1].
....
(18,18)->(18,19)需要的期望回合数是t[19]-t[18]. (18,19)->(19,19)需要的期望回合数是t[19]-t[18].
(19,19)->(19,20)需要的期望回合数是t[20]-t[19]。
全部加起来的结果就是t[19]*2+t[20]-t[19].
所以最后的复杂度可以是线性的,而且理论上对于k个账号也是适用的,这样就可以避开了高斯消元的做法了。
#pragma warning(disable:4996)
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#define ll long long
#define maxn 10000
#define maxe 30000
#define inf 0x3f3f3f3f
using namespace std; double p; double t[25]; int main()
{
while (cin >> p){
t[0] = 0;
t[1] = 1 / p;
t[2] = 1 / p + 1 / (p*p);
for (int i = 3; i <= 20; i++){
t[i] = 1 / p + 1 / p*t[i - 1] - (1 - p) / p*t[i - 3];
}
double ans = t[19] * 2 + t[20] - t[19];
printf("%.6lf\n", ans);
}
return 0;
}
HDU4870 Rating(概率)的更多相关文章
-
hdu4870 Rating (高斯消元或者dp)
Rating Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submi ...
-
HDU 4870 Rating 概率DP
Rating Time Limit:5000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Submit Statu ...
-
HDU4870:Rating(DP)
Problem Description A little girl loves programming competition very much. Recently, she has found a ...
-
hdu 4870 Rating
题目链接:hdu 4870 这题应该算是概率 dp 吧,刚开始看了好几个博客都一头雾水,总有些细节理不清楚,后来看了 hdu 4870 Rating (概率dp) 这篇博客终于有如醍醐灌顶,就好像是第 ...
-
HDU 4870 Rating (2014 多校联合第一场 J)(概率)
题意: 一个人有两个TC的账号,一开始两个账号rating都是0,然后每次它会选择里面rating较小的一个账号去打比赛,每次比赛有p的概率+1分,有1-p的概率-2分,当然如果本身是<=2分的 ...
-
HDU 4870 Rating(概率、期望、推公式) &;&; ZOJ 3415 Zhou Yu
其实zoj 3415不是应该叫Yu Zhou吗...碰到ZOJ 3415之后用了第二个参考网址的方法去求通项,然后这次碰到4870不会搞.参考了chanme的,然后重新把周瑜跟排名都反复推导(不是推倒 ...
-
2014多校第一场J题 || HDU 4870 Rating(DP || 高斯消元)
题目链接 题意 :小女孩注册了两个比赛的帐号,初始分值都为0,每做一次比赛如果排名在前两百名,rating涨50,否则降100,告诉你她每次比赛在前两百名的概率p,如果她每次做题都用两个账号中分数低的 ...
-
Rating
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission ...
-
hdu 4870 Rating(可能性DP&;amp;高数消除)
Rating Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Su ...
随机推荐
-
Android 采用Layout Inflater创建一个View对象
接着上文<Android ListViewview入门>,本文使用android的Inflater来实现 在layouyt文件夹中新建一个list_item.xml的文件,添加如下代码: ...
-
Apache Storm 与 Spark:对实时处理数据,如何选择【翻译】
原文地址 实时商务智能这一构想早已算不得什么新生事物(早在2006年*中就出现了关于这一概念的页面).然而尽管人们多年来一直在对此类方案进行探讨,我却发现很多企业实际上尚未就此规划出明确发展思路 ...
-
HDU 2669 第六周 I题
Description The Sky is Sprite. The Birds is Fly in the Sky. The Wind is Wonderful. Blew Throw the ...
-
随机森林——Random Forests
[基础算法] Random Forests 2011 年 8 月 9 日 Random Forest(s),随机森林,又叫Random Trees[2][3],是一种由多棵决策树组合而成的联合预测模型 ...
-
【HDOJ】4902 Nice boat
区间线段树.题目还不错. /* */ #include <iostream> #include <string> #include <map> #include & ...
-
Javascript 精髓整理篇之二(函数篇)postby:http://zhutty.cnblogs.com
今天总结的内容是javascript的function, 涉及到function顺便讲讲this. Function 是javascript的函数,也是js的执行单元.函数是JavaScript的一种 ...
-
MySQL的常用SQL语句.md
修改密码 这是常见的大家一般都要用的 首先 安装成功了打开cmd --> mysql -u root -p -->输入你的密码 修改mysql root用户密码 格式 ...
-
Java高级开发工程师面试——多线程
来自:Sanesee 链接:http://www.sanesee.com/article/java-engineer-interview-of-thread 1.进程和线程的区别? 进程是一个具有独立 ...
-
安装Office2010出现MSXML版本6.10.1129.0错误
在键盘上按“win+R”组合键出现图图示界面后,输入“regsvr32 /u msxml6.dll”,点击“确定”. 出现图示显示后,点击“确定”,并同时去试试office是否能够安装了. 如果上 ...
-
Postman runner参数化
按照下面图片的顺序操作吧~ lets go 1.把要做参数化的字段的value用花括号标识起来,如:{{phone}} 2.准备一个csv的文件,把每次请求接口的参数按下图填写好,第一行写字段名称(p ...