HDU 4870 Rating(高斯消元)

HDU 4870 Rating

题目链接

题意:一个人注册两个账号,初始rating都是0,他每次拿低分的那个号去打比赛,赢了加50分,输了扣100分,胜率为p,他会打到直到一个号有1000分为止,问比赛场次的期望

思路:f(i, j)表示i >= j,第一个号i分,第二个号j分时候,达到目标的期望,那么可以列出转移为f(i, j) = p f(i', j') + (1 - p) f(i'' + j'') + 1
f(i', j')对应的是赢了加分的状态,f(i'', j'')对应输的扣分的状态,可以把50分当作一个单位,一共有20 * 21 / 2 = 210个状态,也就是对应了210个方程组,利用高斯消元去求解方程组,解出f(0, 0)就是答案

代码:

#include #include #include #include using namespace std; const double eps = 1e-9; const int N = 305; double p, a[N][N]; int mark[25][25]; double solve() { for (int i = 0; i eps) break; for (int j = 0; j eps) { double x = a[j][i] / a[i][i]; for (int k = i; k

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:hdu 2066 一个人的旅行
下一篇:HDU 4869 Turn the pokers
相关文章

Max Sum &&http://acm.hdu.edu.cn/s

hdu 1003 Max Sum

HDU 4007

hdu1856并查集

HDU2094

hdu 1089 Robotic Sort

hdu 1754

HDU 4028

http://acm.hdu.edu.cn/showproblem.p

HDU 4022

图文推荐
HDU 4870 Rating(高斯消元)
ZOJ 3640 Help Me
HDU 4870 Rating(高斯消元)
CF 518C(Anya and
HDU 4870 Rating(高斯消元)
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2012-01-05 人气:2
本文关键词:
分享到:

相关文章

  • hdu 4870 Rating(概率DP&高数消元) 2012-03-07

    Rating Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 714 Accepted Submission(s): 452 Special Judge Problem Description A little girl loves programming competition very much. Recently, she has f

  • POJ 2135 Farm Tour && HDU 2686Matrix && HDU 3376Matrix Again 费用流求来回最短路 2012-04-29

    累了就要写题解,最近总是被虐到没脾气。 来回最短路问题貌似也可以用DP来搞,不过拿费用流还是很方便的。 可以转化成求满流为2 的最小花费。一般做法为拆点,对于 i 拆为2*i 和 2*i+1,然后连一条流量为1(花费根据题意来定) 的边来控制每个点只能通过一次。 额外添加source和sink来控制满流为2。 代码都雷同,以HDU3376为例。 #include #include #include #include #include #include #include #include #inc

  • UVa 133 The Dole Queue 2012-02-24

    The Dole Queue In a serious attempt to downsize (reduce) the dole queue, The New National Green Labour Rhinoceros Party has decided on the following strategy. Every day all dole applicants will be placed in a large circle, facing inwards. Someone is

  • HDU 1811-Rank of Tetris(拓扑排序+并查集) 2012-06-12

    Rank of Tetris Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5221 Accepted Submission(s): 1465 Problem Description 自从Lele开发了Rating系统,他的Tetris事业更是如虎添翼,不久他遍把这个游戏推向了全球。 为了更好的符合那些爱好者的喜好,Lele又想了一个新点子

  • HDU 4864 Task 2012-09-06

    题目链接:HDU 4864 Task Task Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 843 Accepted Submission(s): 185 Problem Description Today the company has m tasks to complete. The ith task need xi minutes

  • hdu 1520Anniversary party(简单树形dp) 2014-03-08

    Anniversary party Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4310 Accepted Submission(s): 1976 Problem Description There is going to be a party to celebrate the 80-th Anniversary of the Ural

  • hdu 1693 Eat the Trees (插头dp入门) 2012-01-01

    Eat the Trees Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2507 Accepted Submission(s): 1225 Problem Description Most of us know that in the game called DotA(Defense of the Ancient), Pudge is a

  • HDU 2571 命运 2012-01-01

    题意:给出一个矩阵,要求从1,1走到n,m,每个格子里都有一定的幸运值,每次只能向下或向右走,如果当前格子是(x,y),下一步可以是(x+1,y),(x,y+1)或者(x,y*k) 其中k>1。 求走到n,m能得到的最大幸运值. 算一道简单的dp题吧. 设dp[i][j]为走到i,j位置能得到的最大值. 那么dp[i][j]=max(dp[i][j - 1], dp[i - 1][j], max{dp[i][k] k满足 k | j 也就是整除j}). 初始化dp为负无穷. dp[1][1

  • hdu 4975 最大流及其唯一性判定(有向图环判断算法升级) 2012-01-02

    就当时最大流再次复习吧。。动手敲一下。。。经典解法不想说了。。这题主要是坑时间,10个提交7个tle。 环的判断,曾经用简单dfs方法,这次的就tle了!别人说要用很?诺?inic,我感觉自己dinic不可能超时,坚信是判断环慢了,于是学习了新断环的方法:删除点/边!从某点进去,若该点的所有边都遍历过还是无功而返,那么该店以后不用再进入了(这么简单的道感觉自己应该要想到啊!愚蠢啊!)开始时用只删除边,还是tle!nb!于是自己删点又删边,一下到156ms,前5了! #include #inclu

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.050 (s). 10 q(s)