P1850 换教室
斯德哥尔摩
2018-10-29 21:12:39
[P1850 换教室](https://www.luogu.org/problemnew/show/P1850)
首先，$Floyd$跑出每对教室之间的最短路。
由于$V\leq 300$，所以可行。
但是然后呢？
这种概率期望题绝对和$DP$逃不了关系。。。
于是开始想$DP$。
本蒟蒻一开始设$dp[i][j]$表示到了第$i$个时间段，申请了$j$门课程到另外的教室，所能达到的期望值。
但是推转移方程时发现要$O(n^3)$转移。。。
因为我们并不知道前面选了哪$j$门课程。。。
具体来说，我们不知道上一次选了哪门课程，只能暴力枚举。。。
于是改一下：
设$dp[i][j][0/1]$表示到了第$i$个时间段，申请了$j$门课程到另外的教室，$0/1$表示第$i$门课程有没有申请到另外的教室，所能达到的期望值。
然后就可以推转移方程了。
我用$path[i][j]$表示$i,j$两个教室之间的最短路。
先考虑不到另外的教室：
如果$i-1$时没有换教室，那么$i-1$到$i$只有一种情况就是都不换教室；
如果$i-1$时换了教室，那么就有两种情况：$i-1$换成功了，或者没换成功。
所以就是对应的路径长乘上对应的概率。
方程：
$$dp[i][j][0]=\min\left\{\begin{array}{}dp[i-1][j][0]+path[c_{i-1}][c_i],\\\\dp[i-1][j][1]+path[c_{i-1}][c_i]\times(1-k_{i-1})\\+path[d_{i-1}][c_i]\times k_{i-1}\end{array}\right.$$
再考虑申请到另外的教室：
显然对于$i-1$可以是$k==0\|k==1$。
对于$k==0$有两种情况，$k==1$有四种情况，就不一一分析了。
列成方程如下：
$$dp[i][j][1]=\min\left\{\begin{array}{}dp[i-1][j-1][0]+path[c_{i-1}][c_i]\times(1-k_i)\\+path[c_{i-1}][d_i]\times k_i\\\\dp[i-1][j-1][1]+path[d_{i-1}][d_i]\times k_{i-1}\times k_i\\+path[d_{i-1}][c_i]\times k_{i-1}\times(1-k_i)\\+path[c_{i-1}][d_i]\times(1-k_{i-1})\times k_i\\+path[c_{i-1}][c_i]\times(1-k_{i-1})\times(1-k_i)\end{array}\right.$$
最终答案显然是：
$$\min\left\{\begin{array}{}dp[n][i][0]\\dp[n][i][1]\end{array}\right.,i\in[0,m]$$
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 2010
#define MAXM 310
#define MAX 999999999
using namespace std;
int n,m,V,E,c=1;
int path[MAXM][MAXM];
double ans=(1LL<<62),dp[MAXN][MAXN][2];
struct Time{
int c,d;
double k;
}a[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void floyd(){
for(int k=1;k<=V;k++)
for(int i=1;i<=V;i++)
for(int j=1;j<=V;j++)
path[i][j]=min(path[i][j],path[i][k]+path[k][j]);
}
void work(){
int x1,x2,y1,y2;
double w1,w2,w3,w4;
dp[1][0][0]=dp[1][1][1]=0;
for(int i=2;i<=n;i++){
x1=a[i-1].c;y1=a[i-1].d;x2=a[i].c;y2=a[i].d;
w1=path[x1][x2];w2=path[x1][y2];w3=path[y1][x2];w4=path[y1][y2];
dp[i][0][0]=dp[i-1][0][0]+w1;
for(int j=1;j<=i&&j<=m;j++){
dp[i][j][0]=min(dp[i][j][0],
min(dp[i-1][j][0]+w1,
dp[i-1][j][1]+w1*(1.00-a[i-1].k)+w3*a[i-1].k
)
);
dp[i][j][1]=min(dp[i][j][1],
min(dp[i-1][j-1][0]+w1*(1.00-a[i].k)+w2*a[i].k,
dp[i-1][j-1][1]+
w4*a[i-1].k*a[i].k+w3*a[i-1].k*(1.00-a[i].k)+
w2*(1.00-a[i-1].k)*a[i].k+w1*(1.00-a[i-1].k)*(1.00-a[i].k)
)
);
}
}
for(int i=0;i<=m;i++)ans=min(ans,min(dp[n][i][0],dp[n][i][1]));
printf("%.2lf\n",ans);
}
void init(){
int u,v,w;
n=read();m=read();V=read();E=read();
for(int i=1;i<=n;i++)a[i].c=read();
for(int i=1;i<=n;i++)a[i].d=read();
for(int i=1;i<=n;i++)scanf("%lf",&a[i].k);
for(int i=1;i<=V;i++)
for(int j=1;j<=V;j++)
path[i][j]=(i==j?0:MAX);
for(int i=1;i<=E;i++){
u=read();v=read();w=read();
if(u==v)continue;
path[u][v]=path[v][u]=min(path[u][v],w);
}
floyd();
memset(dp,127,sizeof(dp));
}
int main(){
init();
work();
return 0;
}
```