题解 P1850 【换教室】
ShineEternal
2019-10-25 19:04:14
[$My\ blog$](https://blog.csdn.net/kkkksc03)
天哪这道题真的是神仙。。。
orz出题人
能出这种dp转移都写吐血的题目真的tql
## description:
给出n个时间段，可申请m次换课，每次换课可申请从$c[i]$换到$d[i]$,并有$k[i]$的概率换课成功，每个教室有间距，问路程期望的最小值。
## solution：
首先这就是一道期望dp题。
说到期望，
https://45475.blog.luogu.org/mathematical-expectation
这篇日报大概会给你不少的启发。
**考虑Dp**
设$f[i][j][0/1]$表示前i节课申请了j次，第i次是否申请的期望最优解。
则：
$$f[i][j][0]=\min(f[i][j][0],f[i-1][j][0]+a[c[i-1]][c[i]],f[i-1][j][1]+(1-k[i-1])*a[c[i-1]][c[i]]+k[i-1]*a[d[i-1]][c[i]])$$
从两种情况转移而来：
- 上一次没申请换课，那么这两次直接都从$c$的规定走就行了。
- 上一次申请换课了：
1、通过了，那么就从上一次的d到现在的c
2、没通过，跟上一次没申请一样
$$f[i][j][1]=\min(f[i][j][1],f[i-1][j-1][0]+k[i]*a[c[i-1]][d[i]]+(1-k[i])*a[c[i-1]][c[i]],f[i-1][j-1][1]+k[i-1]*k[i]*a[d[i-1]][d[i]]+k[i-1]*(1-k[i])*a[d[i-1]][c[i]]+(1-k[i-1])*k[i]*a[c[i-1]][d[i]]+(1-k[i-1])*(1-k[i])*a[c[i-1]][c[i]])$$
### 重要提示：
dp式子真的很长，当然放在代码里写的应该比较短，会尽全力解释，但可以移步代码查看分步式子。
还是分两种：
- 上一次没申请：
1、这次通过了，那么从上一次的c到现在的d
2、没通过，c到c
- 上一次申请了：
~~现在热闹了~~
上一次申请的两种情况：
$$(1-k[i-1])\times c[i-1],k[i-1]*d[i-1]$$
这次申请的两种情况：
$$(1-k[i])\times c[i],k[i]*d[i]$$
现在，只要两两组合即可，共有$2\times2=4$种来源。
**a数组是什么？**
这是两点间距离数组，观察到教室数较少，Floyd求出即可
## code：
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
double k[2005],a[305][305];
double f[2005][2005][2];
int c[2005],d[2005];
int main()
{
int n,m,v,e;
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]);
}
for(int i=1;i<=301;i++)
{
for(int j=1;j<=301;j++)
{
a[i][j]=1000000000;
}
}
for(int i=1;i<=300;i++)
a[i][i]=0;
for(int i=1;i<=e;i++)
{
int x,y;
double z;
scanf("%d%d%lf",&x,&y,&z);
a[x][y]=a[y][x]=min(a[x][y],z);
}
for(int kk=1;kk<=v;kk++)
{
for(int i=1;i<=v;i++)
{
for(int j=1;j<=v;j++)
{
a[i][j]=min(a[i][j],a[i][kk]+a[kk][j]);
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
f[i][j][0]=f[i][j][1]=1000000000;
}
}
f[1][0][0]=f[1][1][1]=0;
for(int i=2;i<=n;i++)
{
for(int j=0;j<=min(i,m);j++)
{
f[i][j][0]=min(f[i][j][0],f[i-1][j][0]+a[c[i-1]][c[i]]);
f[i][j][0]=min(f[i][j][0],f[i-1][j][1]+(1-k[i-1])*a[c[i-1]][c[i]]+k[i-1]*a[d[i-1]][c[i]]);
if(j)
{
f[i][j][1]=min(f[i][j][1],f[i-1][j-1][0]+k[i]*a[c[i-1]][d[i]]+(1-k[i])*a[c[i-1]][c[i]]);
f[i][j][1]=min(f[i][j][1],f[i-1][j-1][1]+k[i-1]*k[i]*a[d[i-1]][d[i]]+k[i-1]*(1-k[i])*a[d[i-1]][c[i]]+(1-k[i-1])*k[i]*a[c[i-1]][d[i]]+(1-k[i-1])*(1-k[i])*a[c[i-1]][c[i]]);
}
}
}
double ans=1000000000;
for(int i=0;i<=m;i++)
{
ans=min(ans,f[n][i][1]);
ans=min(ans,f[n][i][0]);
}
printf("%.2lf\n",ans);
return 0;
}
```