概率dp练习 (16.04.25)
继续练习之旅，记录3道概率dp的题。希望自己从中收获并成长。 zoj 3822 Domination http://www.icpc.moe/onlinejudge/showProblem.do?problemCode=3822 大意：一天放一个棋子到棋盘中，最后要求每一行每一列至少一个棋...
【概率dp】Divide by Zero 2017 and Codeforces Round #399 (Div. 1 + Div. 2, combined) D. Jon and Orbs
直接暴力dp就行……f(i,j)表示前i天集齐j种类的可能性。不超过10000天就能满足要求。#include<cstdio>using namespace std;#define EPS 1e-10int K,q,p;double f[10010][1010];int main(){/...
codeforces 261B Maxim and Restaurant(概率DP)
B. Maxim and Restaurant time limit per test 2 seconds memory limit per test 256 megabytes input standard i...
概率DP（放棋子）Domination
题意：https://zoj.pintia.cn/problem-sets/91827364500/problems/91827369874给你n*m的棋盘，我们定义放满棋盘是：任意一行一列至少有一个棋子。问你放满棋盘需要棋子的期望数。思路：我们先算出用x个棋子放满棋盘的概率，然后求Sigma就可以...
zoj 3822 Domination 概率dp 2014牡丹江站D题
DominationTime Limit: 8 Seconds Memory Limit: 131072 KB Special JudgeEdward is the headmaster of Marjar University. He is enthusiastic about...
HDU 4336——Card Collector——————【概率dp】
Card CollectorTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3407 Accepted Submission(s): ...
动态规划之经典数学期望和概率DP
起因：在一场训练赛上。有这么一题没做出来。题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6829题目大意：有三个人，他们分别有\(X，Y，Z\)块钱（\(1<=X,Y,Z<=1e6\))，钱数最多的（如果不止一个那么随机等概率的选一个）随机...
UVa 11468 Substring AC自动机+概率DP
题目来源：UVA 11468 Substring 题意：求不包含任意一个模式串的长度为l的文本串的概率 给出可以使用的字符的种类及其概率 思路：AC自动机+概率DP #include <cstdio>#include <cstring>#include <queue...
UVa 11427 Expect the Expected (数学期望 + 概率DP)
题意：某个人每天晚上都玩游戏，如果第一次就䊨了就高兴的去睡觉了，否则就继续直到赢的局数的比例严格大于 p，并且他每局获胜的概率也是 p，但是你最玩 n 局，但是如果比例一直超不过 p 的话，你将不高兴的去睡觉，并且以后再也不玩了，现在问你，平均情况下他玩几个晚上游戏。 析：先假设第一天晚上就不高兴的...
UVa 1637 Double Patience (概率DP)
题目 题目大意 \(36\)张牌分成\(9\)堆, 每堆\(4\)张牌。每次可以拿走某两堆顶部的牌, 但需要点数相同。如果有多种拿法则等概率的随机拿。例如, \(9\)堆顶部的牌分别为KS, KH, KD, 9H, 8S, 7C, 7D, 6H, 则有\(5\)种拿法(KS, KH), (KS, K...
UVa11427 - Expect the Expected（概率期望+dp）
题目链接 简介： 每天晚上你都会玩纸牌游戏，如果第一次就赢了就高高兴兴的去睡觉，如果输了就继续玩，假设每盘游戏你获胜的概率都是p。你是一个固执的完美主义者，一定会玩到当晚获胜局数的比例严格大于p时才停止，然后高高兴兴的去睡觉，当然晚上的时间有限，所以你最多只能玩n局，如果获胜比例一直无法超过...
UVA 11468 Substring(AC自动机+概率DP)
UVA 11468 Substring(AC自动机+概率DP) 题意： 给出一个单词字典，然后给出这个字典的所有字符以及其相应的出现概率，现在要随机生成一个长度为L的字符串s，问你s中没有字典中的任意一个单词的概率是多少？ 分析：详见刘汝佳:训练指南P218 构造完改...
UVA 1541 - To Bet or Not To Bet 记忆化DP概率
Alexander Charles McMillan loves to gamble, and during his last trip to the casino he ran across a new game. It is played on a linear sequence of squa...
UVa 11468 Substring (AC自动机+概率DP)
题意：给出一个字母表以及每个字母出现的概率。再给出一些模板串S。从字母表中每次随机拿出一个字母，一共拿L次组成一个产度为L的串，问这个串不包含S中任何一个串的概率为多少？析：先构造一个AC自动机，然后随机生成L个字母，就是在AC自动机的某个结点走多少步，dp[i][j] 表示在 i 结点，并且剩下 ...
POJ 3744 【矩阵快速幂优化 概率DP】
搞懂了什么是矩阵快速幂优化....这道题的重点不是DP./*题意：小明要走某条路，按照个人兴致，向前走一步的概率是p，向前跳两步的概率是1-p，但是地上有地雷，给了地雷的x坐标，（一维），求小明安全到达最后的概率。思路：把路分成好多段，小明安全走完每一段的概率乘起来就是答案。dp[i]=p*dp[i...
hdu4336 Card Collector 概率dp（或容斥原理？）
题意：买东西集齐全套卡片赢大奖。每个包装袋里面有一张卡片或者没有。已知每种卡片出现的概率 p[i]，以及所有的卡片种类的数量 n(1<=n<=20)。问集齐卡片需要买东西的数量的期望值。一开始，自己所理解的期望值是原来学过的 一个值*它自身发生的概率，这没错，但是不知道在这一题里面 那...
[hdu4405]Aeroplane chess(概率dp)
题意：某人掷骰子，数轴上前进相应的步数，会有瞬移的情况，求从0到N所需要的期望投掷次数。解题关键：期望dp的套路解法，一个状态可以转化为6个状态，则该状态的期望，可以由6个状态转化而来。再加上两个状态的消耗即可。 #include<cstdio> #include<cstring&...
HDU4405 Aeroplane chess (概率DP,转移)
http://acm.hdu.edu.cn/showproblem.php?pid=4405题意：在一个1×n的格子上掷色子，从0点出发，掷了多少前进几步，同时有些格点直接相连，即若a，b相连，当落到a点时直接飞向b点。求走到n或超出n期望掷色子次数分析：简单的题目，拿来入门很不错：如果没有飞机的线...
LightOJ - 1151 Snakes and Ladders(概率dp+高斯消元)
有100个格子，从1开始走，每次抛骰子走1~6，若抛出的点数导致走出了100以外，则重新抛一次。有n个格子会单向传送到其他格子，G[i]表示从i传送到G[i]。1和100不会有传送，一个格子也不会有两种传送。问走到100的期望值。 题目链接 我们不难推出方程 但是由于dp值之间的前后影响 我们需要用...
CodeForces 24 D.Broken robot（概率DP+高斯消元）
Description 给出一个 n×m n × m 的矩阵区域，一个机器人初始在第 x x 行第 y y ...