bzoj 4872: [Shoi2017]分手是祝愿 [期望DP]
4872: [Shoi2017]分手是祝愿题意：n个灯开关游戏，按i后i的约数都改变状态。随机选择一个灯，如果当前最优策略\(\le k\)直接用最优策略。问期望步数\(\cdot n! \mod 1003\)50% n=k 送分...从大到小选就行了...实际上送了80分...这个期望DP没想到不...
CERC2017 Gambling Guide，最短路变形，期望dp
题意给定一个无向图，你需要从1点出发到达n点，你在每一点的时候，使用1个单位的代价，随机得到相邻点的票，但是你可以选择留在原地，也可以选择使用掉这张票，问到达n点的最小代价的方案的期望是多少。 分析 dp [i] : 从I 到 n 需要coin 数量的期望显然 dp[n]=0。...
[Codeforces 865C]Gotta Go Fast(期望dp+二分答案)
[Codeforces 865C]Gotta Go Fast(期望dp+二分答案)题面一个游戏一共有n个关卡，对于第i关，用a[i]时间通过的概率为p[i],用b[i]通过的时间为1-p[i]，每通过一关后可以选择继续下一关或者时间清0并从第一关开始，先要求通过所有关卡的时间和不能超过R才算彻底通关...
Painting The Wall 期望DP Codeforces 398_B
B. Painting The Walltime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputUser ainta decided to paint a...
BZOJ5197:[CERC2017]Gambling Guide(最短路,期望DP)
Description 给定一张n个点，m条双向边的无向图。 你要从1号点走到n号点。当你位于x点时，你需要花1元钱，等概率随机地买到与x相邻的一个点的票，只有通过票才能走到其它点。 每当完成一次交易时，你可以选择直接使用那张票，也可以选择扔掉那张票然后再花1元钱随...
[最短路][期望DP]luogu P1850 换教室
https://www.luogu.org/problemnew/show/P1850 分析 先全部跑一边dij，把距离求出来 我们设f[i][j][0/1]表示第i个时段，用了j次换教室机会，当前教室有无使用机会的最小期望 $f[i+1][j][0]=min(f[i][j][0]+dis[c[i]...
CERC2017 Gambling Guide，最短路变形，期望dp
题目链接 题面链接 题意 给定一个无向图，你需要从 1 1 点出发到达 n n 点，你在每一点的时候，使用 1 1 个单位的代价，随机得到相邻点的票，但...
动态规划之经典数学期望和概率DP
起因：在一场训练赛上。有这么一题没做出来。题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6829题目大意：有三个人，他们分别有\(X，Y，Z\)块钱（\(1<=X,Y,Z<=1e6\))，钱数最多的（如果不止一个那么随机等概率的选一个）随机...
UVa 11427 Expect the Expected (数学期望 + 概率DP)
题意：某个人每天晚上都玩游戏，如果第一次就䊨了就高兴的去睡觉了，否则就继续直到赢的局数的比例严格大于 p，并且他每局获胜的概率也是 p，但是你最玩 n 局，但是如果比例一直超不过 p 的话，你将不高兴的去睡觉，并且以后再也不玩了，现在问你，平均情况下他玩几个晚上游戏。 析：先假设第一天晚上就不高兴的...
UVa11427 - Expect the Expected（概率期望+dp）
题目链接 简介： 每天晚上你都会玩纸牌游戏，如果第一次就赢了就高高兴兴的去睡觉，如果输了就继续玩，假设每盘游戏你获胜的概率都是p。你是一个固执的完美主义者，一定会玩到当晚获胜局数的比例严格大于p时才停止，然后高高兴兴的去睡觉，当然晚上的时间有限，所以你最多只能玩n局，如果获胜比例一直无法超过...
[BZOJ4872][六省联考2017]分手是祝愿(期望DP)
4872: [Shoi2017]分手是祝愿Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 516 Solved: 342[Submit][Status][Discuss]DescriptionZeit und Raum trennen dich un...
[六省联考2017]分手是祝愿（期望+DP）
题解很容易想出来最优策略是什么。就是从n到1看到开着的灯就把它关了我们预处理出当前状态把灯全部关闭后的最少步数cnt然后我们的主人公就要瞎按。。。设dp[i]代表当前状态最优解为i步时走到dp[i-1]用过步数的期望。现在我们考虑如何转移到dp[i]当我们这一步走到当前最优策略的一步时。dp[i]=...
HDU4405 Aeroplane chess(期望dp)
题意抄袭自https://www.cnblogs.com/Paul-Guderian/p/7624039.html正在玩飞行棋。输入n,m表示飞行棋有n个格子，有m个飞行点，然后输入m对u,v表示u点可以直接飞向v点,即u为飞行点。如果格子不是飞行点，扔骰子(1~6等概率)前进。否则直接飞到目标点。...
bzoj2878: [Noi2012]迷失游乐园 基环树dp求路径期望
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;#define N 110000int e[N],ne[N*2],v...
Codeforces.24D.Broken robot(期望DP 高斯消元)
题目链接 可能这儿的会更易懂一些（表示不想再多写了）。 令\(f[i][j]\)表示从\((i,j)\)到达最后一行的期望步数。那么有\(f[n][j]=0\)。 若\(m=1\)，答案是\(2(n-x)\)。 否则，显然有\[f[i][1]=\frac13(f[i+1][1]+f[i][1]+f...
Codeforces1097D. Makoto and a Blackboard（数论+dp+概率期望）
题目链接：传送门题目大意：给出一个整数n写在黑板上，每次操作会将黑板上的数（初始值为n）等概率随机替换成它的因子。问k次操作之后，留在黑板上的数的期望。要求结果对109+7取模，若结果不是整数，则用分数表示，并对109+7取逆元。（1 ≤ n ≤ 1015， 1 ≤ k ≤ 104）思路：首先我们要...
Problem Arrangement ZOJ - 3777(状压dp + 期望)
ZOJ - 3777就是一个入门状压dp期望dp[i][j]当前状态为i，分数为j时的情况数然后看代码 有注释#include <iostream>#include <cstdio>#include <sstream>#include <cstring&g...
hdu4035 Maze 【期望dp + 数学】
题目链接BZOJ4035题解神题啊。。。orz不过网上题解好难看，数学推导不写\(Latex\)怎么看。。【Latex中毒晚期】我们由题当然能很快写出\(dp\)方程设\(f[i]\)表示从\(u\)出发逃离的期望步数，\(m\)为该点度数\[\begin{aligned}f[u] &= K...
BZOJ_3143_[Hnoi2013]游走_期望DP+高斯消元
BZOJ_3143_[Hnoi2013]游走_期望DP+高斯消元题意：一个无向连通图，顶点从1编号到N，边从1编号到M。 小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选 择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z 到达N号顶点时游走...
codeforces 352D - Jeff and Furik【期望dp】
首先恋人操作过一轮之后逆序对不会变多，所以设f[i]为把i个逆序对消掉的期望次数，f[i]=0.5f[i-2]+0.5f[i]+2，化简然后递推即可 #include<iostream>#include<cstdio>using namespace std;const int...