基本概念与基础数学知识
数学知识：概率与期望
简单的对概率期望做理解性的解释。
概率就是某一件事发生的可能性。注意对某两件事是否是相同一件事的判定。
这件事的发生可能会与之前的选择有关，例如上一步操作或这一步的选择。
期望就是对某件事产生的结果进行的平均值。可以将每一步的选择的概率乘以相应的权值，再累加起来所有选择的和得到。
如果把概率与期望抽象成图，那么针对图的每一个点，他的出度就是将自己的概率分散到孩子节点所除的分母。换句话说，这个节点的概率由自己的入度和父亲节点的概率决定。而期望就是每一条路的权乘以目标点的概率（这也是为什么期望dp常常以i+1作为循环赋值单位）
概率与期望dp的基本概念
就是对概率进行dp的过程，在dp过程中计算期望。有时会针对不同的物品引入不同的其他相关知识点（例如组合数）
解题思路
一般来说分为三类：
方法一：直接根据期望公式定义期望状态
全期望公式：
将期望图进行抽象计算，\(G_i\)表示从i点发出的边的集合
方法二：利用期望的线性性质
线性性质：
采用刷表的方式转移。起点的概率为100%，递推式为：（dp(i)为概率）
\[dp(e_{to})=dp(e_u) \times \dfrac{1}{|G_u|} \]适用范围很广。
方法三：利用期望公式的线性计算
有的时候题目的状态数少但是构造图的分支极多，这时考虑dp最常规的多维dp构造法。
假设某一件事的概率为p，如果只有两个状态，因此：
注意此时的全期望其实是所有的期望图的叶子节点相加，因此不可在计算概率时计算期望，要在最后根据某一维的最大值计算全期望。
例题引入
例一：P4316 绿豆蛙的归宿
题目链接：P4316
简单观察发现期望图很好构造，就是图本身。但是由于初始状态确定顺推，结束状态确定逆推，本题中将dp(i)作为从节点i到终点的期望长度，自然dp(n)=0，所以末状态确定，用逆推，反向建图。
#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[u];i;i = edge[i].next){
int v = edge[i].to ;
in[v]-- ;
f[v] += (f[u] + 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[u]++ ,degree[u]++ ;
}
topo(n) ;
printf("%.2lf" , f[1]) ;
return 0 ;
}
但其实，正向做也不是不可以，此时演变成了第二种思路，就是稍微慢了一点。
#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[u];i;i = edge[i].next){
int v = edge[i].to ,w = edge[i].w ;
f[v] += f[u] / degree[u] ;
ans += f[u] / degree[u] * 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[u]++ ;in[v]++ ;
}
}
topo(1) ;
printf("%.2lf\n" , ans) ;
return 0 ;
}
例二：CF 518D Ilya and Escalator
这个题构造图后发现非常复杂(\(2^n\)个节点)但是一个人只有上不上、什么时候上两种状态。考虑第三种方法。
直接上代码。
#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维度的本质是因变量，从这下手构造就好！
此题最好的方法就是第二种。
#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[u][v] = map[v][u] = min(w , map[v][u]) ;
}
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构造法
- 找准顺逆推、初始状态与结束状态
优质blogs:sengxian
标签：专题,期望,int,edge,MAXN,include,dp From： https://www.cnblogs.com/adolf-stalin/p/17064972.html