基本概念与基础数学知识

数学知识：概率与期望

简单的对概率期望做理解性的解释。
概率就是某一件事发生的可能性。注意对某两件事是否是相同一件事的判定。
这件事的发生可能会与之前的选择有关，例如上一步操作或这一步的选择。
期望就是对某件事产生的结果进行的平均值。可以将每一步的选择的概率乘以相应的权值，再累加起来所有选择的和得到。
如果把概率与期望抽象成图，那么针对图的每一个点，他的出度就是将自己的概率分散到孩子节点所除的分母。换句话说，这个节点的概率由自己的入度和父亲节点的概率决定。而期望就是每一条路的权乘以目标点的概率（这也是为什么期望dp常常以i+1作为循环赋值单位）

概率与期望dp的基本概念

就是对概率进行dp的过程，在dp过程中计算期望。有时会针对不同的物品引入不同的其他相关知识点（例如组合数）

解题思路

一般来说分为三类：
方法一：直接根据期望公式定义期望状态
全期望公式：dp(i)=\sum_{e\in G_i} \dfrac{dp(e_{to})+e_{cost}}{|G_i|}

将期望图进行抽象计算，

$𝐺_{𝑖}$ 表示从i点发出的边的集合
方法二：利用期望的线性性质
线性性质：

𝐸 [𝑋 + 𝑌] = 𝐸 [𝑋] + 𝐸 [𝑌]

采用刷表的方式转移。起点的概率为100%，递推式为：（dp(i)为概率）

𝑑 𝑝 (𝑒_{𝑡 𝑜}) = 𝑑 𝑝 (𝑒_{𝑢}) \times \frac{1}{| 𝐺_{𝑢} |}

适用范围很广。
方法三：利用期望公式的线性计算
有的时候题目的状态数少但是构造图的分支极多，这时考虑dp最常规的多维dp构造法。
假设某一件事的概率为p，如果只有两个状态，因此：

𝑑 𝑝 (𝑖 + 1, 𝑗 + 1) = 𝑑 𝑝 (𝑖, 𝑗) \times 𝑝 [发 生 了]

𝑑 𝑝 (𝑖 + 1, 𝑗) = 𝑑 𝑝 (𝑖, 𝑗) \times (1 - 𝑝) [未 发 生]

注意此时的全期望其实是所有的期望图的叶子节点相加，因此不可在计算概率时计算期望，要在最后根据某一维的最大值计算全期望。

例题引入

例一：P4316 绿豆蛙的归宿

题目链接：P4316
简单观察发现期望图很好构造，就是图本身。但是由于初始状态确定顺推，结束状态确定逆推，本题中将dp(i)作为从节点i到终点的期望长度，自然dp(n)=0，所以末状态确定，用逆推，反向建图。

highlighter- Go

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std ;

const int MAXN = 2e5+10 ;

int n ,m ;
int head[MAXN] ;int edge_cnt = 1 ;
struct Edge{
	int w ;
	int to ;
	int next ;
}edge[MAXN] ;
int in[MAXN] ,degree[MAXN] ;
double f[MAXN] ;

inline void add(int from , int to , int w){
	edge[edge_cnt].to = to ;
	edge[edge_cnt].next = head[from] ;
	edge[edge_cnt].w = w ;
	head[from] = edge_cnt++ ;
}

bool vis[MAXN] ;
inline void topo(int sta){
	queue<int> q ;
	q.push(sta) ;
	while(q.empty() == false){
		int u = q.front() ;q.pop() ;
		for(int i = head;i;i = edge[i].next){
			int v = edge[i].to ;
			in[v]-- ;
			f[v] += (f + edge[i].w) / degree[v] ;//目的地的入度可能数 就是 转移的概率 			if(in[v] == 0)	q.push(v) ;
		}
	}
}

int main(){
	scanf("%d%d" , &n , &m) ;
	for(int i = 1;i <= m;++i){
		int u ,v ,w ;
		scanf("%d%d%d" , &u , &v , &w) ;
		add(v , u , w) ;//返向建图 		in++ ,degree++ ;
	}
	
	topo(n) ;
	
	printf("%.2lf" , f[1]) ;
	return 0 ;
}

但其实，正向做也不是不可以，此时演变成了第二种思路，就是稍微慢了一点。

highlighter- Go

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std ;

const int MAXN = 2e5+10 ;

struct Edge{
    int to ,next ,w ;
}edge[MAXN] ;
int head[MAXN] ,edge_cnt = 1 ;
inline void add(int from , int to , int w){
    edge[edge_cnt].to = to ;
    edge[edge_cnt].next = head[from] ;
    edge[edge_cnt].w = w ;
    head[from] = edge_cnt++ ;
}

int m ,n ;
double f[MAXN] ,ans = 0 ;
int degree[MAXN] ,in[MAXN] ;

inline void topo(int sta){
    queue<int>  q ;
    memset(f , 0 , sizeof f) ;
    q.push(sta) ;
    f[sta] = 1 ;
    while(!q.empty()){
        int u = q.front() ;q.pop() ;
        for(int i = head;i;i = edge[i].next){
            int v = edge[i].to ,w = edge[i].w ;
            f[v] += f / degree ;
            ans += f / degree * w ;
            if(--in[v] == 0)   q.push(v) ;
        }
    }
}

int main(){
    while(~scanf("%d%d" , &n , &m)){
        for(int i = 1;i <= m;++i){
            int u ,v ,w ;
            scanf("%d%d%d" , &u , &v , &w) ;
            add(u , v , w) ;
            degree++ ;in[v]++ ;
        }
    }
    topo(1) ;
    printf("%.2lf\n" , ans) ;
    return 0 ;
}

例二：CF 518D Ilya and Escalator

这个题构造图后发现非常复杂( $2^{𝑛}$ 个节点)但是一个人只有上不上、什么时候上两种状态。考虑第三种方法。
直接上代码。

highlighter- Go

#include<iostream>
#include<cstdio>
using namespace std ;

const int MAXN = 2e3+10 ;
double f[MAXN][MAXN] ,p ;
int n ,t ;

int main(){
	scanf("%d%lf%d" , &n , &p , &t) ;
	
	f[0][0] = 1 ;
	
	for(int i = 0;i < t;++i){
		f[i+1][n] += f[i][n] ;
		for(int j = 0;j < n;++j){
			f[i+1][j+1] += f[i][j] * p ;
			f[i+1][j] += f[i][j] * (1 - p) ;
		}
	}
	
	double ans = 0 ;
	for(int i = 0;i <= n;++i)
		ans += f[t][i] * i ;
	printf("%lf" , ans) ;
	return 0 ;
}

当然，这道题还是可以用起始状态一定的方法做的，只不过会慢一点，这里不详细展开。

例三：P1850 [NOIP2016 提高组] 换教室

注意不要让模板局限住了思维！dp维度的本质是因变量，从这下手构造就好！
此题最好的方法就是第二种。

highlighter- Go

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std ;

const int MAXN = 2004 ;

int n ,m ,e ,v ;
double map[MAXN][MAXN] ;
double k[MAXN] ;
int c[MAXN] ,d[MAXN] ;
double f[MAXN][MAXN][2] ;

inline double min(double a , double b){
	return a > b ? b : a ;
}

int main(){
	scanf("%d%d%d%d" , &n , &m , &v , &e) ;
	for(int i = 1;i <= n;++i)	scanf("%d" , c+i) ;
	for(int i = 1;i <= n;++i)	scanf("%d" , d+i) ;
	for(int i = 1;i <= n;++i)	scanf("%lf" , k+i) ;
	
	memset(map , 0x7f , sizeof map) ;
	memset(f , 0x7f , sizeof f) ;
	for(int i = 1;i <= v;++i)
			map[i][i] = map[i][i] = 0 ;
			
	for(int i = 1;i <= e;++i){
		int u ,v ,w ;
		scanf("%d%d%d" , &u , &v , &w) ;
		map[v] = map[v] = min(w , map[v]) ;
	}
	for(int i = 1;i <= n;++i) map[i][i] = 0 ;
	
	for(int k=1;k<=v;k++)
		for(int i=1;i<=v;i++)
    		for(int j=1;j<i;j++)
        		if(map[i][k] + map[k][j] < map[i][j]) map[i][j] = map[j][i] = map[i][k] + map[k][j] ;
	
	f[1][0][0] = f[1][1][1] = 0 ;
	for(int i = 2;i <= n;++i){
		double delta1 = map[c[i-1]][c[i]] ;
		double delta2 = map[d[i-1]][c[i]] ;
		double delta3 = map[c[i-1]][d[i]] ;
		double delta4 = map[d[i-1]][d[i]] ;
		for(int j = 0;j <= m;++j){
			f[i][j][0] = min(f[i-1][j][0] + delta1 , f[i-1][j][1] + delta2 * k[i-1] + delta1 * (1 - k[i-1])) ;
			//				上次不换       正常路程  上次概率换了的  换了的路程       正常路程  失败的概率 			if(j)
			f[i][j][1] = min(f[i-1][j-1][0] + delta3 * k[i] + delta1 * (1 - k[i]) , 
			//               上次不换   这次换了的路程  成功概率   失败路程   失败概率 					f[i-1][j-1][1] + delta1 * (1 - k[i]) * (1 - k[i-1]) + delta3 * (1 - k[i-1]) * k[i] + delta2 * (1 - k[i]) * k[i-1] + delta4 * k[i-1] * k[i]) ;
			//                 上次换了         正常路程  失败概率    上次也失败     上失这成  上次失败概率  这成概率  上成  这失概率     上成概率   双成     概率  		}
	}
	
	double ans = 9999999999 ;
    for(int i = 0;i <= m;++i)
    	ans = min(f[n][i][0] , min(f[n][i][1] , ans)) ;
	
    printf("%.2lf" , ans) ;
	return 0 ;
}

总结归纳

构造期望图
时刻牢记dp构造法
找准顺逆推、初始状态与结束状态