概率与期望
引入：一个普通骰子，求投出点数的期望。 \[E=\sum_i p_i w_i\] 其中，\(p_i\) 表示事件 \(i\) 发生的概率，\(w_i\) 表示事件 \(i\) 发生的收益，\(E\) 为收益期望。 在这个题中，\(E=\dfrac{1}{6}\times1+\dfrac{1}{6}\times2+\cdots+\dfrac{1}{6}\times6=3.5\)。
期望的线性性
现有 \(3\) 个骰子，求投一次这 \(3\) 个骰子的点数之和的期望。对于本题，只要分别求出这 \(3\) 个骰子的期望并加起来就可以了。这就是期望的线性性。 \[E(x+y)=E(x)+E(y)\] 若 \(x\) 和 \(y\) 相互独立，则 \[E(x)E(y)=E(xy)\] 对于常数 \(k\) ，有 \[E(kx)=kE(x)\]
解题方式
解决期望问题一般使用 DP 或高斯消元。
例题 1
现有 \(1\) 个按钮，每按一次就会等概率返回 Yes 或 No，期望按多少次会返回 Yes？ 答案为 \(2\)。 考虑第一次返回 Yes 的概率为 \(\dfrac{1}{2}\)，第二次返回 Yes 的概率为 \(\dfrac{1}{4}\)，第三次为 \(\dfrac{1}{8}\)…… 则 \(E=\dfrac{1}{2}\times 1+\dfrac{1}{4}\times 2+\dfrac{1}{8}\times 3+\cdots=2\)。
例题 2
有 \(n\) 种不同的邮票，想收集所有种类的邮票，每次只能买一张，且买到任何一种邮票是等概率的，为 \(\dfrac{1}{n}\)。每次购买花费 \(1\) 元钱。现手中没有邮票，求买到所有种类邮票所花费钱数的期望。 考虑 DP。设 \(f_x\) 表示已集齐 \(x\) 张时的期望次数。对于第 \(i\) 次购买，有 \(\dfrac{i}{n}\) 的概率买重，\(\dfrac{n-i}{n}\) 的概率不重。 \[f_i=1+f_i\times \dfrac{i}{n}+f_{i+1}\times \dfrac{n-i}{n}\] 化简，得 \[f_{i+1}=\dfrac{n}{n-i}-f_i\]
例题 3
有 \(n\) 个奖品，\(m\) 个人排队选礼物。对于每个人，他打开的盒子可能有礼物，也可能已经被之前的人取走。如果有礼物，取走礼物并放回盒子。求所有人期望取走多少个礼物。 考虑 DP。设 \(f_i\) 表示前 \(i\) 个人取走礼物个数的期望，则有 \[f_1=1,f_i=f_{i-1}+\dfrac{n-f_{i-1}}{n}\] 或者考虑 \(1\) 个礼物被拿走的概率，用 \(n\) 乘上它即为答案。一个礼物被一个人拿走的概率为 \(\dfrac{n-1}{n}\)，进行 \(m\) 轮，为 \((\dfrac{n-1}{n})^m\)，则答案为 \(n\times [1-{(\dfrac{n-1}{n})}^m]\)。
例题 4
假设第 \(i\) 位之前有 \(q\) 个连续 \(1\)，则这个位置的贡献为 \((q+1)^3-q^3=3q^2+3q+1\)。 所以我们需要维护 \(q\) 和 \(q^2\) 的期望。 \[E_i(q)=p_i(E_{i-1}(q)+1)\] \[E_i(q^2)=p_i(E_{i-1}(q^2)+2E_{i-1}(q)+1)\] 总式子 \[f_i=f_{i-1}+p_i(3E_{i-1}(q^2)+3E_{i-1}(q)+1)\] 已经很详细了就不放代码了。
例题 5
解决任意两个教室之间的体力消耗最小值，容易想到最短路算法，因本题需要多次查询不同两点间的最短路且
\(v\) 较小，考虑使用 Floyd。 之后就是
DP，对每种情况进行分类讨论，设 \(f_{i,j,0/1}\) 表示对于前 \(i\) 门课，选择了 \(j\) 门，最后选择的那门课否/是更换。\(dis_{u,v}\) 表示 \(u\) 和 \(v\) 两点之间的最短路。 那么进行分类讨论
对于 \(f_{i,j,0}\)，若其之前的换了，则有 \(f_{i-1,j,1}+k_{i-1}\times
dis_{d_{i-1},c_i}\)（换成功的期望）\(+(1-k_{i-1})\times
dis_{c_{i-1},c_i}\)（换失败的期望），若之前的没换，则有 \(f_{i-1,j,0}+dis_{c_{i-1},c_i}\)（二者都不换）。
对于 \(f_{i,j,1}\)，情况复杂些 -
之前的不换 - 当前换成功 \(k_i\times
dis_{c_{i-1},d_i}\) - 当前换失败 \((1-k_i)\times dis_{c_{i-1},c_i}\) -
之前的换 - 之前与当前均成功 \(k_{i-1}\times
k_i\times dis_{d_{i-1},d_i}\) - 之前与当前均失败 \((1-k_{i-1})\times (1-k_i)\times
dis_{c_{i-1},c_i}\) - 之前成功当前失败 \(k_{i-1}\times (1-k_i)\times
dis_{d_{i-1},c_i}\) - 之前失败当前成功 \((1-k_{i-1})\times k_i\times
dis_{c_{i-1},d_i}\) 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
using namespace std;
const int N=2010,M=90010;
int n,m,v,e;
int c[N],d[N],edge[310][310];
double k[N],dp[2010][2010][2],ans;
int main(){
memset(edge,0x3f,sizeof(edge));
scanf("%d%d%d%d",&n,&m,&v,&e);
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
dp[i][j][0]=dp[i][j][1]=1145141919810;
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);
for(int i=1;i<=e;i++){
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
edge[a][b]=min(edge[a][b],w);
edge[b][a]=min(edge[b][a],w);
}
for(int i=1;i<=v;i++)
edge[i][i]=0;
for(int k1=1;k1<=v;k1++)
for(int i=1;i<=v;i++)
for(int j=1;j<=v;j++)
edge[i][j]=min(edge[i][j],edge[i][k1]+edge[k1][j]);
dp[1][0][0]=dp[1][1][1]=0;
for(int i=2;i<=n;i++)
for(int j=0;j<=m;j++){
dp[i][j][0]=min(dp[i-1][j][1]+k[i-1]*edge[d[i-1]][c[i]]+
(1-k[i-1])*edge[c[i-1]][c[i]],
dp[i-1][j][0]+edge[c[i-1]][c[i]]);
if(j){
dp[i][j][1]=min(dp[i-1][j-1][1]+k[i-1]*k[i]*edge[d[i-1]][d[i]]+
k[i-1]*(1-k[i])*edge[d[i-1]][c[i]]+
(1-k[i-1])*k[i]*edge[c[i-1]][d[i]]+
(1-k[i-1])*(1-k[i])*edge[c[i-1]][c[i]],
dp[i-1][j-1][0]+k[i]*edge[c[i-1]][d[i]]+
(1-k[i])*edge[c[i-1]][c[i]]);
}
}
ans=1145141919810;
for(int i=0;i<=m;i++)
ans=min(ans,min(dp[n][i][0],dp[n][i][1]));
printf("%.2lf",ans);
return 0;
}
例题 6
考虑第 \(i\) 道题和第 \(i+1\) 道题。 若 \(a_i=a_{i+1}\)，则本题期望显然为 \(\dfrac{1}{a_i}=\dfrac{1}{a_{i+1}}\)。 若
\(a_i>a_{i+1}\)，则 \(a_i\) 的答案在 \(a_{i+1}\) 范围内的概率为 \(\dfrac{a_{i+1}}{a_i}\)，期望为 \(\dfrac{a_{i+1}}{a_i}\times
\dfrac{1}{a_{i+1}}=\dfrac{1}{a_i}\)。 若 \(a_i<a_{i+1}\)，正确答案在 \(a_{i}\) 范围内的概率为 \(\dfrac{a_i}{a_{i+1}}\)，期望为 \(\dfrac{a_i}{a_{i+1}}\times
\dfrac{1}{a_i}=\dfrac{1}{a_{i+1}}\)。 综上，第 \(i\) 道题的期望为 \(\dfrac{1}{\max(a_i,a_{i+1})}\)。求出每题期望累加即可。
1
2
3
4a[0]=a[n];//第一项的上一个是第n项
for(int i=1;i<=n;i++)
ans+=1.0/max(a[i-1],a[i]);
printf("%.3lf",ans);