题解 P1850 【换教室】
皎月半洒花
2018-04-12 19:37:53
$9.10upd$:我才发现我写错汉语描述了……真是越来越优秀了啊……
$\rm{First}$ $\rm{of}$ $\rm{all}$ , 我自认为这篇题解写的比大佬们要详细……比较适合提高组的新手$OIer$阅读$qwq$
嗯，这是我的第一篇期望的题解……这是本蒟蒻第一次一眼看出$DP$方程和预处理$qwq$，纪念一下！
但实际上，是$rqy$帮我解决的这道题的关键部分……此致敬礼$qwq$
那么对于这篇题解，我的定义是，没有什么优化，只是最简单的求解这个问题而已。至于优化什么的，本蒟蒻不会呀$qwq$.
那么对于这道题而言，先捋清楚题目是求什么的吧：
对于这个无向连通图，我们将每走一步定义为一个阶段。那么每一个阶段都有两种可能性：$p_i$的概率去$d_i$，但是在所有的$d[i]$ 中$(1<=i<=n)$至多可以走$m$个，$(1-p_i)$的概率去$c[i]$。而我们要求的，就是在这$n$个阶段结束之后的路程最小期望。
那么其实状态之间的转移，我们不难看出有两种状态的转移：从$d[i-1]$或从$c[i-1]$转移过来。而因为实际上对于这个$DP$而言，因为数据不大，所以不需要优化什么的$qwq$，记录每种状态是可行的。
那么很显然啊，我们首先要预处理出每两个点之间的最短路来，方便状态的转移。而在这里，最简单的就是$Floyd$啊$qwq$。$(n^3$显然可以接受$)$
```cpp
for(qwq int k=1;k<=v;k++)
for(qwq int i=1;i<=v;i++)
for(qwq int j=1;j<i;j++)
if(f[i][k]+f[k][j]<f[i][j])
f[i][j]=f[j][i]=f[i][k]+f[k][j];
```
然后就是$DP$方程了:
### 我们定义$dp[i][j][0/1]$来表示当前为第$i$个阶段，连同这一次已经用了$j$次换教室的机会，当前这次换$(1)$不换$(0)$的最小期望路程总和。
那么转移就可以如此转移：
这次不换：
$dp[i][j][0]=$ $min($上次不换的$dp+$这两次之间的路程 $~~$， $~~$上次概率换了之后的$dp+p[i - 1]\times$上次换了的教室与这次不换的教室之间的距离$+(1-p[i - 1])\times$上次不换的教室与这次不换的教室之间的距离$)$
“诶，为什么上次概率换了之后（即逗号之后的一大串）要加两个期望啊？”
这个问题就是$rqy$大佬给我解决的，现在我要农夫山泉一把了：因为在上一次换教室时是**“概率”**交换，所以不一定会换呀。所以要把两种情况的都加上$qwq$。
到这儿我们就可以发现，其实换教室比不换教室是要多一重状态的，因为换教室总要牵扯**“概率成功”**的问题$qwq$
那其实接下来的状态转移方程就很简单了：一次换一次不换，遇到不换就$(1-p[i])$，遇到换就$p[i]$；两次都不换就不用枚举概率。而且由于牵扯到两次都是概率性事件（比如两次都换）之类的，这个时候需要的就是乘法原理了。
那么$DP$即如下：
```cpp
#define qwq register
for(qwq int i=2;i<=n;i++){
double add1=f[c[i-1]][c[i]];
for(qwq int j=0;j<=min(m,i);j++)
{
dp[i][j][0]=min(dp[i-1][j][0]+add1,dp[i-1][j][1]+f[d[i-1]][c[i]]*p[i-1]+f[c[i-1]][c[i]]*(1-p[i-1]));
if(j!=0)
dp[i][j][1]=min(dp[i-1][j-1][0]+f[c[i-1]][d[i]]*p[i]+f[c[i-1]][c[i]]*(1-p[i]),dp[i-1][j-1][1]+f[c[i-1]][c[i]]*(1-p[i-1])*(1-p[i])+f[c[i-1]][d[i]]*(1-p[i-1])*p[i]+f[d[i-1]][c[i]]*(1-p[i])*p[i-1]+f[d[i-1]][d[i]]*p[i-1]*p[i]);
}
}
```
总结：遇到期望的题目时一定要全面考虑啊！我们可以发现这个题的$dp$方程其实并不难想。
完结撒花！
```cpp
//感谢rqy大佬qwqqq
#include<iostream>
#include<cstdio>
#define qwq register
using namespace std;
double p[10001],f[2001][2001],dp[2001][2001][2];
int a[2001][2001],c[20001],d[20001];
inline double min(double a,double b){
return a<b?a:b;
}
inline int qread(){
int k = 0;
char c;
c = getchar();
while(!isdigit(c))c = getchar();
while(isdigit(c)){
k = (k<<1)+(k<<3)+c-48;
c = getchar();
}
return k ;
}
int main()
{
int n,m,v,e,a1,b1,c1;
cin>>n>>m>>v>>e;
for(qwq int i=1;i<=n;i++)c[i]=qread();
for(qwq int i=1;i<=n;i++)d[i]=qread();
for(qwq int i=1;i<=n;i++)cin>>p[i];
for(qwq int i=1;i<=v;i++)
for(qwq int j=1;j<i;j++)
f[i][j]=f[j][i]=999999999;
for(qwq int i=1;i<=e;i++){
a1=qread(),b1=qread(),c1=qread();
f[a1][b1]=f[b1][a1]=min(f[a1][b1],c1);
}
for(qwq int k=1;k<=v;k++)
for(qwq int i=1;i<=v;i++)
for(qwq int j=1;j<i;j++)
if(f[i][k]+f[k][j]<f[i][j])
f[i][j]=f[j][i]=f[i][k]+f[k][j];
for(qwq int i=1;i<=n;i++)
for(qwq int j=0;j<=m;j++)
dp[i][j][0]=dp[i][j][1]=999999999;
dp[1][0][0]=dp[1][1][1]=0;
for(qwq int i=2;i<=n;i++){
double add1=f[c[i-1]][c[i]];
for(qwq int j=0;j<=min(m,i);j++)
{
dp[i][j][0]=min(dp[i-1][j][0]+add1,dp[i-1][j][1]+f[d[i-1]][c[i]]*p[i-1]+f[c[i-1]][c[i]]*(1-p[i-1]));
if(j!=0)
dp[i][j][1]=min(dp[i-1][j-1][0]+f[c[i-1]][d[i]]*p[i]+f[c[i-1]][c[i]]*(1-p[i]),dp[i-1][j-1][1]+f[c[i-1]][c[i]]*(1-p[i-1])*(1-p[i])+f[c[i-1]][d[i]]*(1-p[i-1])*p[i]+f[d[i-1]][c[i]]*(1-p[i])*p[i-1]+f[d[i-1]][d[i]]*p[i-1]*p[i]);
}
}
double hahaha=9999999999;
for(int i=0;i<=m;i++){
hahaha=min(dp[n][i][0],min(dp[n][i][1],hahaha));}
printf("%.2lf",hahaha);
}
```
## $By$ $Flower$ _ $pks$