DP&图论 DAY 4 上午

DP&图论  DAY 4  上午

概率与期望

概率
◦某个事件A发生的可能性的大小，称之为事件A的概率，记作P(A)。
◦假设某事的所有可能结果有n种，每种结果都是等概率，事件A涵盖其中
的m种，那么P(A)=m/n。
◦例如投掷一枚骰子，点数小于3的概率为2/6=1/3。

◦如果两个事件A和B所涵盖的结果没有交集，那么P(A或B发生)=P(A)+P(B)
◦还是掷骰子
◦ P(点数小于3或点数大于4)=2/6+2/6=2/3
◦如果A和B所涵盖的结果有交集
◦那么P(A或B发生)=P(A)+P(B)-P(A与B同时发生)
◦ P(点数小于3或点数为偶数)=2/6+3/6-1/6=2/3

◦记事件B为“事件A不发生”
◦那么P(A)+P(B)=1，即P(B)=1-P(A)
◦ P(点数不小于3)=1-2/6=2/3
◦在两个互不干扰的事中，事件A在其中一件事中，事件B在另外一件事中
◦那么P(A与B同时发生)=P(A)*P(B)
◦掷两个骰子， P(第一个点数小于3且第二个点数为偶数)=(2/6)*(3/6)=1/6

期望
◦事件A有多种结果，记其结果的大小为x，那么x的期望值表示事件A的结
果的平均大小，记作E(x)。
◦ E(x)=每种结果的大小与其概率的乘积的和。
◦例如，记掷一枚骰子的点数为x
◦ E(x)=1*(1/6)+2*(1/6)+3*(1/6)+4*(1/6)+5*(1/6)+6*(1/6)=7/2
◦若c为常数，那么：
◦ E(x+c)=E(x)+c， E(c*x)=c*E(x)

◦记两个事件的结果分别为x,y
◦ E(x+y)=E(x)+E(y)
◦例如： E(语文成绩+数学成绩)=E(语文成绩)+E(数学成绩)

就好比一个四维的骰子

◦若两个事件互相独立， E(x*y)=E(x)*E(y)
◦ E(语文成绩*数学成绩)=E(语文成绩)*E(数学成绩)

概率和期望的计算
◦概率与期望的计算有一个共同的计算技巧：
◦若事件所产生的所有方案都是等概率的，那么一些概率与期望即可转化
为一个计数问题，算出后再除以总方案数即可。
◦如求事件符合条件A的概率，则转化为对符合A的方案数的计数问题；若
求方案的某种价值的期望值，则转化为所有方案的价值总和的计数问题。

◦概率与期望的计算也经常用的其加法和乘法规则。
◦尤其是期望的加法规则，在期望的计算中十分常用。 如求最大值与最小
值之差的期望，则分别求二者的期望值再作差即可。
◦应用乘法规则时，要注意事件是否互相独立。

◦概率与期望还可以通过列方程的方法计算。
◦有4张卡片，写着0,1,2,3，每次抽出一张并放回，反复抽，抽出0为止。问
抽取的次数的期望值。
◦设抽取次数为x，则：
◦ x=1+x*3/4  
◦ x=4

（解释一下列的方程：

x为抽取的次数

然后一定要抽一次，答案贡献1

然后你有1/4的几率抽到0，游戏终止，还需要抽 1/4 * 0 次

3/4的几率没抽到0，还要继续抽，就又回到了当前问题，还需要抽 3/4 * x 次

x = 1 + 1/4 * 0 + 3/4 * x

x = 1 + 3/4 * x

x = 4

....over )

（或者是这样理解：

设抽取的次数为x

1.   每次抽取的时候就有1/4的几率抽到0，游戏终止 ，实际操作1 ，对应：   1/4 * 1

2.   3/4的几率没有抽到0，然后继续下一轮，面临的还是原问题，所以还是会有 x 的答案，但是这个当前抽的这一次由于，没抽到0，所以是白抽了，但是还是要算进答案去，所以就是x+1 ，对应：   3/4 *（x+1）

所以    x = 1/4 + 3/4*(x+1)

x = 1/4 + 3/4 + 3/4*x

x = 1 + 3/4*x

解得    x = 4

.....over ）

◦比较常见一种计算方法就是概率dp与期望dp。

概率DP期望DP

>Solution

◦比较简单的概率dp
◦设f[i][j]为小球经过第i行第j列的概率。
◦ f[1][1]=1 （即起状态概率为1
◦ f[i][j] = f[i-1][j-1] * [(i-1,j-1)有钉子]*1/2
◦           +f[i-1][j] * [(i-1,j)有钉子]*1/2
◦           +f[i-2][j-1] * [(i-2,j-1)没有钉子]
◦至于分数输出，自定义分数数据类型并用gcd化简分数即可

> Bzoj5004 开锁魔法II
◦有 n 个箱子，每个箱子里有且仅有一把钥匙，每个箱子有且仅有一把钥
匙可以将其打开。现在随机打开 m 个箱子，求能够将所有箱子打开的概
率。
◦ 100组数据， k<=n<=300。

>Solution

◦题目约定了每个点的入度和出度均为1，因此最终的图一定是若干个环。
每个环都至少选择一个点即可满足要求。求概率，实际上就是求方案数，
最后再除以总方案数即可。
◦预处理出每个环的点数 c[i] 以及其后缀和 sum[i] 。
◦设 f[i][j] 表示前 i 个环中选出 j 个点，满足最终条件每个环都选的方案数。
初始化 f[0][0]=1 。
◦枚举 i 和 前 i 个环选的点数 j 、第 i 个环选的点数 k。
◦可得

 >BZOJ5091 摘苹果
◦在花园中有n棵苹果树以及m条双向道路，每条道路的两端连接着两棵不
同的苹果树。假设第i棵苹果树连接着di条道路。小Q将会按照以下方式去
采摘苹果：
◦ 1.随机移动到一棵苹果树下，移动到第i棵苹果树下的概率为di/2m，但不
在此采摘。
◦ 2.重复以下操作k次：等概率随机选择一条与当前苹果树相连的一条道路，
移动到另一棵苹果树下，假设当前位于第i棵苹果树下，则他会采摘ai个苹
果，多次经过同一棵苹果树下会重复采摘。
◦请计算小Q期望摘到多少苹果。 n,k<=100000,m<=200000

 >Solution

E（x1+x2+..+xn）= sigema E(xi)  i 1~n      f(k,i)*ai

x1 是否在第一个苹果树下

f(1,i)  第一轮到 i 的概率 ，di / 2m

每一轮的概率都一样

◦首先容易得到一个简单的做法。
◦设f(i,j)为走i步之后到达j的概率，那么：

◦我们知道

◦那么第一步走每条边的概率都为

◦于是 ，同理得

◦于是

>BZOJ4832 抵制克苏恩
◦你有一个英雄和若干奴隶主，对方每次攻击会从你的英雄和奴隶主中随
机选一个造成一点伤害。奴隶主受到攻击后，体力为0则死亡，否则若场
上奴隶主少于7个，则召唤一个3点血量的奴隶主。
◦有T局游戏，每局给出初始奴隶主的数量(<=7)和血量(<=3)，给出k，求对
方攻击k次后你的英雄受到的总伤害值的期望。
◦ T<=100， k<=50。

>Solution

◦设f[i][a][b][c]表示还要进行i轮攻击，三种血量 1,2,3 的奴隶主数量分别为a,b,c时，
接下来英雄受到的期望总伤害。

◦设f[i][a][b][c]表示还要进行i轮攻击，三种血量的奴隶主数量分别为abc时，
接下来英雄受到的期望总伤害。
◦转移只要枚举当前攻击到的是英雄还是哪种奴隶主即可。
◦初始f[0][a][b][c]=0。
◦每次询问可以O(1)回答。

>NOIP2016 换教室
◦小A的学校可以视为一个v个点的无向图，他有n门课程要按顺序上课，其
中第i门课程要在节点ai进行，但还有一个备选地点bi。
◦现在小A有m个申请机会，若申请第i门课，那么将有ki的概率使课程搬到
bi进行。每门课最多申请一次，而且要在全部申请完成后才知道是否成功，
m次机会不必全部用完。他如何申请才能最小化在上课地点间移动的距离
的期望值。求该期望值。
◦ v<=300， n,m<=2000

>Solution

出的概率为1，但是接受的概率不一定为1

◦首先可以floyd求出任意两点间最短路径。
◦可以想到一个显然的dp状态： f[i][j][0/1]表示前i个课程申请了j次，且第i个
是否申请时的最小期望值。
◦转移示例：
◦ f[i][j][0]=Min{ f[i-1][j][0]+dis(a[i-1],a[i]) ,
◦ f[i-1][j][1]+k[i-1]*dis(b[i-1],a[i])+(1-k[i-1])*dis(a[i-1],a[i])}
◦ f[i][j][1]也是同理，只需要考虑i和i-1都是否申请上即可。
◦时间复杂度O(v^3+nm)

>BZOJ1076 奖励关
◦有n轮游戏和m种宝物，每种宝物有分数Pi（可以为负），每轮游戏会等
概率抛出一种宝物，你可以选择吃或不吃。第i种宝物还有一个限制集合Si，
表示只有在Si中的宝物都吃过后，才能吃第i种宝物。
◦求最优策略下的期望得分。
◦ n<=100， m<=15

>Solution

◦当你要做是否吃某个宝物的决策时，如果你知道以吃或不吃的状态进入
接下来的几轮游戏时分别的期望得分是多少，那么就可以择优进行决策。
◦于是设f[i][S]为还要进行i轮游戏，吃过的宝物集合为S时，接下来能得到的
最大期望得分。
◦ f[i][S]= ( ∑Max{ f[i-1][S] , f[i-1][S∪k]+a[k] } )/m

S∪k--> S|1<<k
◦初始f[0][S]=0。 ans=f[n][0]。

---

最套路的斜率优化

◦斜率优化本身是个很套路的东西。
◦它有一个很标准的形式，以及很套路的解法。

>hdu3507
◦要输出N个数字a[N]，输出的时候可以连续的输出，每连续输出一串，它
的费用是 ：这串数字和的平方加上一个常数M。
◦ 0 ≤ n ≤ 500000, 0 ≤ M ≤ 1000

>Solution

区间DP

dp[i] 到第i个数字最少花费，然后枚举断点

◦ dp设计很简单，主要是优化。
◦我们设dp[i]表示输出到 i 的时候最少的花费， S[i] 表示从 a[1] 到 a[i-1] 的数字
和。注意这里为了方便起见前缀和与一般的有区别，就是让式子看起来
更好看，没别的特殊意义。
◦ dp[i]=min{ dp[j] + ( S[i+1]-S[j]）² + M } (j<i)  ，这个 j 就是断点
◦然后就是O(N^2)复杂度。

>考虑优化

对于上面那个式子

◦那么我们想，能否在O(1)时间内找到所有转移里最优的那个呢？
◦我们假设在求解 dp[i] 时，存在 j , k (j > k，j是前者，k是后者) 使得从j转移比从k转移更优，那么需
要满足条件：
◦                     dp[j]+(S[i+1]-S[j])²+M < dp[k]+(S[i+1]-S[k])²+M
◦展开上式
◦  dp[j]+S[i+1]²-2S[i+1]S[j]+S[j]²+M < dp[k]+S[i+1]²-2S[i+1]S[k]+S[k]²+M
◦移项并消去再合并同类项得
◦               (dp[j]+S[j]²)-(dp[k]+S[k]²) < 2S[i+1](S[j]-S[k])

◦把S[j]-S[k]除过去，得到

◦我们设f[x]=dp[x]+S[x]²，就化成了

◦即当( j>k )时，若

，则 j 对更新 dp[i] 比 k 更新 dp[i] 优。

◦那把 (s[i],f[i]) 看作一个点，左边就是斜率的形式了。
◦当一个数的 dp值 求完了，它的f值也跟着确定，我们就可以在空间中绘制
出点 (s[i],f[i]) 。这个点代表已经求出dp值的一个点。

◦当我们要求解dp[t]时，如果可用的集合里存在这样三个点，位置关系如图所示： 

◦这时候他们和2S[t+1]的关系有3种：

◦那么j比i优， k比j优。

◦那么i比j优， k比j优。

◦那么i比j优， j比k优 。

◦综上，不管什么样的S[t+1]，从j转移都不会是最佳方案。那么用一个数据
结构维护一个凸包（下凸） ，每加入一个点就删去一些点，使其维持凸
包的形态。最优转移一定在这个凸包中。

◦下凸的凸包边斜率增加，上凸的凸包边斜率减小。

◦在凸包里，谁又是最最优呢？
◦首先一定数据结构里的凸包一定会是这样的：

◦ 假设的斜率>2S[t+1]且 的斜率<2S[t+1]

从图形特点我们可以发现 j 点比所有比k小的点都优，比所有比i大的也优。 

◦ 所以对于我们二分查找斜率比 2S[t+1] 小的编号最大的点，就是最优的转移
点。由于S[i]也满足单调性，那么如果一个点不是i的最优点了，那么肯定
也不是i+1的，我们还可以直接维护一个单调队列就能解决这个问题。

◦ 单调队列每次从后加时，维护凸包。
◦ 每次新计算一个i的dp值，从单调队列队首弹出那些不可能再合法的元素。

复杂度O(nlogn)

>推导结束
◦看似推导很多，其实是很套路的，并且很多都是在证明和理解。
◦多做两道题就掌握了。
◦设j>k且j优于k，以此列个式子。
◦推式子的时候，把只与j和k有关放在不等号左边，带i有关的项放在不等式
右边。
◦设出点的坐标。根据推出方程的不等号，是大于号，那么上凸，维护斜
率递减。
◦小于号，下凸，维护斜率递增。

>代码实现

>一模一样的练习题： bzoj3156

>Solution

◦ f[i]=min(f[j]+(i-j-1)*(i-j)/2+a[i])。
◦设k>j，且k优于j。
◦ f[k]+(i-k)*(i-k-1)/2+a[i]<f[j]+(i-j)*(i-j-1)/2+a[i]
◦设K=k+1,J=j+1 为了好推

◦还是和上题一样单调队列维护一个下凸壳即可。 

总结
◦斜率优化其实就是一个优化dp[i]=max/min{f[j]+g[i]*h[j]}+a[i]式子的一个通
用方法。
◦除了推式子的部分。
◦还要保证，推出来等式的右边要单调，不单调，就要在凸壳上二分。
◦等式左边抽象出来的点的X坐标也要单调， Y坐标不需要保证单调。
◦当然其实X不单调和等式右边不单调也都能做，只不过难度较大，需要用
到CDQ分治，或平衡树维护凸包的技巧。

---

常见模型

>bzoj4321
◦编号为1~n的人排成一排，问有多少种排法使得任意相邻两人的编号之差
不为1或-1。
◦ n<=1000

>Solution

f[i][j][0/1]  前 i 个数字中有 j 个相邻对

◦ 老套路了， 排列计数问题考虑把数从小到大插入的过程进行dp。
◦ 设 f[i][j] 表示 1∼i 的排列，有 j 组相邻的相差1，且 i 和 i-1 不相邻的方案数；
◦ 设 g[i][j] 表示 1∼i 的排列，有 j 组相邻的相差1，且 i 和 i-1 相邻的方案数。
◦ 那么考虑插入 i+1 的位置，有：
◦ 不破坏空位且不与 i 相邻、不破坏空位且与 i 相邻、破坏空位且不与 i 相邻、破
坏空位且与 i 相邻（只发生在 g 的转移） 4种。
◦ 分别推一下方案数即可。
◦ 最后的答案就是 f[n][0] 。
◦ 时间复杂度 O(n^2) 。

>BZOJ2560 串珠子
◦有n个珠子，第i和j个珠子之间有c[i][j]条不同的绳子可选。每对珠子之间
可以选择不连绳子，也可以选择用其中一种绳子连接。
◦问有多少种方案能使n个珠子成为连通图。
◦ n<=16

>Solution

总方案-不连通

不连通分类：1号连通了T，T

f[s]

◦连通图计数套路： 用总数减去不连通的方案数，而不连通的方案数，可
以枚举1号点所在连通块的点集（有的问题中是大小） ，用这个点集的连
通方案数乘以剩余点集的总方案数即可。
◦ g[s]表示s点集互相连的所有情况（包括不连边的情况），就是把内部的C
全乘起来， f[s]表示s状态下的合法情况，即使得s状态下所有点连通的合
法情况。答案是f[2^n-1]。
◦ g[s]好求，考虑如何求f[s]， f[s]就是g[s]减去所有的不合法情况。任意一个
不合法的情况一号点肯定在某个联通快内，我们枚举不合法情况1号点所
在的联通块的点集i，那么这里不合法的情况就是g[s^i]*f[i]，我们减去这
些情况，就能求出f[s]了。
◦时间复杂度O(3^n)，也是要枚举子集。 g预处理可以做到n*2^n。

PS：

f[s]合法   g[s] 无所谓

f[s] = g[s] - Σ f[t] * g[s^t]

T∈S

T！=S

S最低位∈T