一道繁琐至极的期望$DP$。

设 $s$ 为概率空间,即题目要求 $E(s)=\sum\limits_{i=1}^nE(X_i)$,这里的 $X_i$ 表示第 $i$个教室, 换不换教室,因此问题是互相独立的。

可以用前缀和 $f_{i,j,0/1}=f_{i-1,j/j-1,0/1}+E(X_i)$ 处理。

跑一跑floyd处理一下最短路。

根据数学期望的定义,对现在处理状态进行计算就好了。

下面是转移方程(概率*随机变量取值)

int x1=c[i-1],x2=d[i-1],y1=c[i],y2=d[i];
f[i][j][0]=min(f[i][j][0],min(f[i-1][j][0]+map[x1][y1],f[i-1][j][1]+map[x2][y1]*p[i-1]+map[x1][y1]*(1-p[i-1])));
f[i][j][1]=min(f[i][j][1],min(f[i-1][j-1][0]+map[x1][y2]*p[i]+map[x1][y1]*(1-p[i]),f[i-1][j-1][1]+map[x2][y2]*p[i-1]*p[i]+map[x1][y2]*(1-p[i-1])*p[i]+map[x2][y1]*p[i-1]*(1-p[i])+map[x1][y1]*(1-p[i-1])*(1-p[i])));