概率dp
YbtOJ 454「概率期望 dp」期望旅行
YbtOJ 454「概率期望 dp」期望旅行 题目链接：YbtOJ #454 小 A 有一张 n 个点的有向图。已知图中 x\rightarrow y 的有向边每天有 a_{x,y} 的概率存在。保证 \forall x,a_{x,x}=1，即所有自环肯定存在。小 A 从 1 号点出发，每天需要选择当前所在点一条 存在 的出边，走到对应的点。求采取最优策略时，从 1 号点走到 n 号点的期望天
日期 2023-06-12 10:48:40
HDU 4089 Activation（概率DP）（转）
11年北京现场赛的题目。概率DP。 公式化简起来比较困难。。。。而且就算结果做出来了，没有考虑特殊情况照样会WA到死的。。。。 去参加区域赛一定要考虑到各种情况。 像概率dp，公式推出来就很容易写出来了。 1 /* 2 HDU 4098 3 题意：有n个人排队等着在官网上激活游戏。Tomato排在第m个。 4 对于队列中的第一个人。有一下情况： 5 1、激活失败，留在
日期 2023-06-12 10:48:40hdu4405--Aeroplane chess（概率dp第七弹：飞行棋游戏--2012年网络赛）
Aeroplane chess Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1628 Accepted Submission(s): 1103
日期 2023-06-12 10:48:40
ZOJ 3822 Domination(概率dp 牡丹江现场赛)
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5376 Edward is the headmaster of Marjar University. He is enthusiastic about chess and often plays chess with his friends. What's
日期 2023-06-12 10:48:40
hdu 3853 LOOPS (概率dp)
/* dp[i][j]表示(i,j)到(R,C)须要消耗的能量 则： dp[i][j]=p1[i][j]*dp[i][j]+p2[i][j]*dp[i][j+1]+p3[i][j]*dp[i+1][j]+2;///+2 转移到下一个能量要消耗2 化简得： dp[i][j]=((p2[i][j]*dp[i][j+1])+(p3[i][j]*dp[i+1][j])+2)/(1-p1[i][j])
日期 2023-06-12 10:48:40
poj 2096 Collecting Bugs 【概率DP】【逆向递推求期望】
Collecting Bugs Time Limit: 10000MS Memory Limit: 64000K Total Submissions: 3523 Accepted: 1740 Case Time Limit: 2000MS Special Judge Desc
日期 2023-06-12 10:48:40【BZOJ3640】JC的小苹果 概率DP+高斯消元
【BZOJ3640】JC的小苹果 Description 让我们继续JC和DZY的故事。 “你是我的小丫小苹果，怎么爱你都不嫌多！” “点亮我生命的火，火火火火火！” 话说JC历经艰辛来到了城市B，但是由于他的疏忽D
日期 2023-06-12 10:48:40UVa 11021 Tribles (概率DP + 组合数学)
题意：有 k 只小鸟，每只都只能活一天，但是每只都可以生出一些新的小鸟，生出 i 个小鸟的概率是 Pi，问你 m 天所有的小鸟都死亡的概率是多少。 析：先考虑只有一只小鸟，dp[i] 表示 i 天全部死亡的概率，那么 dpi] = P0 + P1*dp[i-1] + P2*dp[i-1]^2 + ... + Pn*dp[i-1]^(n-1)，式子 Pjdp[i-1]^j 表示该小鸟生了 j 后代
日期 2023-06-12 10:48:40![BZOJ 1444 [Jsoi2009]有趣的游戏 (AC自动机 + 概率DP + Gauss)](/scriptcss/images/66.png)
BZOJ 1444 [Jsoi2009]有趣的游戏 (AC自动机 + 概率DP + Gauss)
1444: [Jsoi2009]有趣的游戏 Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 1382 Solved: 498[Submit][Status][Discuss] Description Input 注意 是0<=P Output
日期 2023-06-12 10:48:40HDU 5236 Article (概率DP+贪心)
题意：要求输入一篇N个字符的文章，对所有非负整数i：每到第i+0.1秒时可以输入一个文章字符，每到第i+0.9秒时有P的概率崩溃（回到开头或者上一个存盘点） 每到第i秒有一次机会可以选择按下X个键存盘，或者不存，打印完整篇文章之后必须存盘一次才算完成输入多组N,P,X选择最佳策略使得输入完整篇文章时候按键的期望最小， 输出此期望 析：dp[i]表示打完前 i 个字符，概论是多少，dp[i] =
日期 2023-06-12 10:48:40POJ 3071 Football (概率DP)
题意：给定 2的n次方 个团队对每个队的战胜的概率，一块要打 n 场，每场都是 1 对 2， 2 对 3，每次都取赢的一方，问你最后谁是冠军的概率最大。 析：dp[i][j] 表示 第 i 场 j 胜的概率，每次只要算 i 相邻的且不是已经打过的 2 i-1次方个队，最后再选出概率最大的就好。 代码如下： #pragma comment(linker, "/STACK:1024000000,1
日期 2023-06-12 10:48:40UVa 10900 So you want to be a 2n-aire? （概率DP，数学）
题意：一 个答题赢奖金的问题，玩家初始的金额为1，给出n，表示有n道题目，t表示说答对一道题目的概率在t到1之间，每次面对一道题，可以选择结束游戏， 获得当 前奖金；回答下一道问题，答对的概率p在t到1之间，答对的话奖金翻倍，答错的话结束游戏，没有奖金，求玩家赢的奖金的期望值的最大值。 析：首先是求期望，那就和平均值差不多，我们来分析第 i 道题时，两个情况，要么回答，要么不回答，如果不回答那么
日期 2023-06-12 10:48:40HDU 4599 Dice (概率DP+数学+快速幂)
题意：给定三个表达式，问你求出最小的m1，m2,满足G(m1) >= F(n), G(m2) >= G(n). 析：这个题是一个概率DP，但是并没有那么简单，运算过程很麻烦。 先分析F(n)，这个用DP来推公式，d[i]，表示抛 i 次连续的点数还要抛多少次才能完成。那么状态转移方程就是 d[i] = 1/6*(1+d[i+1]) + 5/6*(1+d[1]), 意思就是说在第 i
日期 2023-06-12 10:48:40HDU 3366 Passage (概率DP)
题意：T组测试数据，一个人困在了城堡中，有n个通道，m百万money ，每个通道能直接逃出去的概率为 P[i] ，遇到士兵的概率为 q[i]， 遇到士兵得给1百万money，否则会被杀掉，还有 1-p[i]-q[i] 的概率走不通，要回头。问在可以选择的情况下，逃出去的概率是多少？ 析：这个题很明显是概率DP么，就是不会。。。。在比赛时，读完题，直接放弃。。。。。 最后还是问的学长，是这样的，d
日期 2023-06-12 10:48:40hdu3076ssworld VS DDD 概率dp
//ssworld VS DDD 两个人有血量值 hp1 , hp2 //两人掷骰子得到每一点的概率已知 //ssword赢的概率 //dp[i][j] 表示有第一个人血量为i。第二个人的血量为j第一个人赢的概率 //第一个人赢，第二个人赢 ， 平局的概率为p1 , p2 , p3 //那么有dp[i][j] = p2*dp[i-1][j] + p1*dp[i][j-
日期 2023-06-12 10:48:40hdu4405Aeroplane chess 概率dp水题
//从0到n有n+1个格子 //对于格子i，掷一次骰子的数为x。那么能够从位置i到位置i+x //格子之间有连线，假设格子a和b有连线，那么从a到b不用掷骰子 //求从0到n的骰子掷的次数的期望 //dp[i] = 1/6*segma(dp[k]) + 1 (i<=k<=i+6) #include<cstdio> #include<iostream> #i
日期 2023-06-12 10:48:40【bzoj5004】开锁魔法II 组合数学+概率dp
题目描述 有 $n$ 个箱子，每个箱子里有且仅有一把钥匙，每个箱子有且仅有一把钥匙可以将其打开。现在随机打开 $m$ 个箱子，求能够将所有箱子打开的概率。 题解 组合数学+概率dp 题目约定了每个点的入度和出度均为1，因此最终的图一定是若干个环。每个环都至少选择一个点即可满足要求。 预处理出每个环的点数 $c[i]$ 以及其后缀和 $sum[i]$ 。 设 $f[i][j]$ 表示前 $i$
日期 2023-06-12 10:48:40【bzoj4832】[Lydsy2017年4月月赛]抵制克苏恩 概率期望dp
题目描述 你分别有a、b、c个血量为1、2、3的奴隶主，假设英雄血量无限，问：如果对面下出一个K点攻击力的克苏恩，你的英雄期望会受到到多少伤害。 输入 输入包含多局游戏。 第一行包含一个整数 T (T<100) ，表示游戏的局数。 每局游戏仅占一行，包含四个非负整数 K, A, B 和 C ，表示克苏恩的攻击力是 K ，你有 A 个 1 点血量的奴隶 主， B 个 2 点血量的奴隶主， C
日期 2023-06-12 10:48:40【bzoj3029】守卫者的挑战 概率dp
题目描述 给出一个数$m$和$n$次操作，第$i$操作有$p_i$的概率成功，成功后会使$m$加上$a_i$（$a_i$为正整数或$-1$），求$n$次操作以后成功的操作次数不少于$l$且$m\ge 0$的概率。 输入 第一行三个整数N,L,M。第二行N个实数，第i个实数pi表示第i项挑战成功的百分比。第三行N个整数，第i个整数ai表示第i项挑战的属性值. 输出 一个整数，表示所求概率，四舍五入
日期 2023-06-12 10:48:40【bzoj3566】[SHOI2014]概率充电器 树形概率dp
题目描述 著名的电子产品品牌 SHOI 刚刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI 概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!”SHOI 概率充电器由 n-1 条导线连通了 n 个充电元件。进行充电时,每条导线是否可以导电以概率决定,每一个充电元件自身是否直接进行充电也由概率决定。随后电
日期 2023-06-12 10:48:40【bzoj2318】Spoj4060 game with probability Problem 概率dp
题目描述 Alice和Bob在玩一个游戏。有n个石子在这里，Alice和Bob轮流投掷硬币，如果正面朝上，则从n个石子中取出一个石子，否则不做任何事。取到最后一颗石子的人胜利。Alice在投掷硬币时有p的概率投掷出他想投的一面，同样，Bob有q的概率投掷出他相投的一面。 现在Alice先手投掷硬币，假设他们都想赢得游戏，问你Alice胜利的概率为多少。 输入 第一行一个正整数t，表示数据组数。
日期 2023-06-12 10:48:40