sdut2623--The number of steps（概率dp第一弹，求期望）
The number of stepsTime Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^题目描写叙述Mary stands in a strange maze, the maze looks like a triangle（the first ...
ACM - 概率、期望题目 小结（临时）
概率DP求期望大多数都是全期望公式的运用。主要思考状态空间的划分以及状态事件发生的概率。问题可以分为无环和有环两类。无环一类多数比较简单，可以通过迭代或者记忆化搜索完成。有环一类略复杂，可以通过假设方程化简公式解决或者高斯消元求解。POJ 2096 Collecting Bugshttp://poj...
zoj3640：概率（期望）dp
题目大意：有一个吸血鬼，初始攻击力为f，每天随机走到n个洞里面，每个洞有一个c[i]，如果他的攻击力f>c[i]则可以花费t[i]的时间逃走，否则则花费一天时间使自己的攻击力增加c[i]，求逃走天数的期望分析：这道题求期望，，考虑采用概率dp求解想到的最简单方法就是dp[i][j]表示第i天，...
bzoj 2969: 矩形粉刷 概率期望+快速幂
还是老套路：期望图上的格子数=$\sum$每个格子被涂上的期望=$\sum$1-格子不被图上的概率这样的话就相对好算了.那么，对于$(i,j)$来说，讨论一下上，下，左，右即可.然后发现四个角的面积会被重复统计，所以再减去$4$个角的贡献即可.#include<bits/stdc++.h>...
bzoj 2969: 矩形粉刷 概率期望
题目:为了庆祝新的一年到来，小M决定要粉刷一个大木板。大木板实际上是一个W*H的方阵。小M得到了一个神奇的工具，这个工具只需要指定方阵中两个格子，就可以把这两格子为对角的，平行于木板边界的一个子矩形全部刷好。小M乐坏了，于是开始胡乱地使用这个工具。假设小M每次选的两个格子都是完全随机的（方阵中每个格...
[BZOJ4832]抵制克苏恩(概率期望DP)
方法一：倒推，最常规的期望DP。f[i][a][b][c]表示还要再攻击k次，目前三种随从个数分别为a,b,c的期望攻击英雄次数，直接转移即可。#include<cstdio>#include<cstring>#include<iostream>#include&...
【POJ 2096】Collecting Bugs 概率期望dp
题意有s个系统，n种bug，小明每天找出一个bug，可能是任意一个系统的，可能是任意一种bug，即是某一系统的bug概率是1/s，是某一种bug概率是1/n。求他找到s个系统的bug，n种bug，需要的天数的期望。分析计算期望E=∑所有可能需要的天数*概率找到s个系统n种bug，需要最少max（s，...
LightOJ 1030 Discovering Gold (概率/期望DP)
题目链接：LightOJ-1030DescriptionYouareinacave,alongcave!Thecavecanberepresentedbya\(1\timesN\)grid.Eachcellofthecavecancontainanyamountofgold.Initiallyyou...
【专题】概率期望DP
11.22：保持更新状态：主要发一些相关的题目和个人理解（P.S.如果觉得简单，可以直接看后面的题目）upd11.30更完了【NO.1】UVA12230 CrossingRivers 一道比较坑的题目,多给了一个没用的条件...其实就是利用线性关系，取一个平均值就OK了。把最优情况和最差情况算出来，...
Codeforces 908 D.New Year and Arbitrary Arrangement (概率&期望DP)
题目链接：NewYearandArbitraryArrangement题意：有一个ab字符串，初始为空。 用Pa/(Pa+Pb)的概率在末尾添加字母a，有 Pb/(Pa+Pb)的概率在末尾添加字母b，当出现≥k个ab子串时立即停止添加字母，求最后期望的ab子串个数。（子串ab不要求连续） 例子：当k...
【loj6191】「美团 CodeM 复赛」配对游戏 概率期望dp
题目描述n次向一个栈中加入0或1中随机1个，如果一次加入0时栈顶元素为1，则将这两个元素弹栈。问最终栈中元素个数的期望是多少。输入一行一个正整数n。输出一行一个实数，表示期望剩下的人数，四舍五入保留三位小数。样例输入10样例输出4.168题解概率期望dp显然任何时刻栈中的元素自底至顶一定是若干个0+...
【BZOJ-4008】亚瑟王 概率与期望 + DP
4008:[HNOI2015]亚瑟王TimeLimit:20Sec MemoryLimit:512MBSec SpecialJudgeSubmit:832 Solved:515[Submit][Status][Discuss]Description小K不慎被LL**了，*程度深到他甚至想...
luoguP3750 [六省联考2017]分手是祝愿 概率期望DP + 贪心
...........真的神状态了，没办法去想的状态...................考试的时候选择$50$分贪心+$15$分状压吧，别的点就放弃算了........令$f[i]$表示从最小步数为$i$时走到最小步数为$i-1$的状态的期望步数（所以题目中的$k$实际上是个提示............
bzoj2969 矩形粉刷 概率期望
此题在bzoj是权限题，，，所以放另一个oj的链接题解：因为期望线性可加，所以可以对每个方格单独考虑贡献。每个方格的贡献就为至少被粉刷过一次的概率×1(每个格子的最大贡献就是1...)每个方格至少被粉刷过一次的概率=1-一次都没被粉刷过的概率因为每次选择都不互相影响，因此我们实际上只需要计算对于每一...
UVA 11427 (概率DP+期望)
题目链接: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=35396题目大意：每晚打游戏。每晚中，赢一局概率p，最多玩n局，如果最后不能保证胜率大于p，则从此不玩。问打游戏的天数的期望。解题思路：首先分析每天晚上的。设f[i]...
hdu-5810 Balls and Boxes(概率期望)
题目链接：BallsandBoxesTimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/65536K(Java/Others)ProblemDescriptionMr.Chopsticksisinterestedinrandomphenom...
概率期望dp
对于概率dp，我一直都弄得不是特别明白，虽然以前也有为了考试去突击过，但是终究还是掌握得不是很好，所以决定再去学习一遍，把重要的东西记录下来。1.hdu4405Description在一个\(1*n\)的格子上掷色子，从\(0\)点出发，掷了多少前进几步，同时有些格点直接相连，即若\(a\)，\(b...
Codeforces - 1264C - Beautiful Mirrors with queries - 概率期望dp
一道挺难的概率期望dp，花了很长时间才学会div2的E怎么做，但这道题是另一种设法。https://codeforces.com/contest/1264/problem/C要设为\(dp_i\)表示第\(i\)个格子期望经过多少次，所以\(dp_{n+1}=1\)。https://www.cnbl...
【bzoj4832】[Lydsy2017年4月月赛]抵制克苏恩 概率期望dp
题目描述你分别有a、b、c个血量为1、2、3的奴隶主，假设英雄血量无限，问：如果对面下出一个K点攻击力的克苏恩，你的英雄期望会受到到多少伤害。输入输入包含多局游戏。第一行包含一个整数T(T<100)，表示游戏的局数。每局游戏仅占一行，包含四个非负整数K,A,B和C，表示克苏恩的攻击力是K，你有...
【BZOJ-1419】Red is good 概率期望DP
1419:RedisgoodTimeLimit: 10Sec MemoryLimit: 64MBSubmit: 660 Solved: 257[Submit][Status][Discuss]Description桌面上有R张红牌和B张黑牌，随机打乱顺序后放在桌面上，开始一张一张地翻牌，翻到红牌...