-1 感谢
-
参考题解(逃 -
感谢zzy学长讲解的期望dp。
0 预知识
期望和dp
1 设计状态
我们很容易想到用
[f_{i,j}
]
表示前(i)次课申请换了(j)次教室的最短路程。但这样是没办法转移的。
这时就需要一个想法:设状态
[f_{i,j,0/1}
]
表示前(i)次课申请换了(j)次教室的最短路程,并且第(i-1)次课有(1)没有(0)申请换教室。
2 转移
这样的话就好转移了。我们设
[C1=c_{i-1},C2=d_{i-1},C3=c_i,C4=d_i
]
确实是ViXbob题解上的,别喷我啊qwq
那方程就是
其实想好了状态之后方程就一目了然了。具体解释见代码。其实自己手玩一下直接就出来了嘛
3 代码
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int inf = 5e8;
const int N = 2001;
const int V = 301;
int n,m,v,e;
int c[N],d[N];
int dis[V][V];
double k[N];
double f[N][N][2];
double ans=inf;
inline void readx(int &x)
{
x=0; int s=-1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') s=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
x*=s;
}
inline void Init()
{
scanf("%d%d%d%d",&n,&m,&v,&e);
for(int i=1;i<=v;++i) for(int j=1;j<=v;++j) dis[i][j]=inf;
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,_c;scanf("%d%d%d",&_a,&_b,&_c);dis[_a][_b]=dis[_b][_a]=min(dis[_a][_b],_c);}
//这里千万记得判重边,这个重边贼恶心人!!!
for(int i=1;i<=v;++i) dis[i][i]=0;
for(int k=1;k<=v;++k)
for(int i=1;i<=v;++i)
for(int j=1;j<=v;++j)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
for(int i=1;i<=n;++i)
for(int j=0;j<=m;++j)
f[i][j][0]=f[i][j][1]=inf;
f[1][0][0]=f[1][1][1]=0;
}
//理解一下应该能看懂
inline void DP()
{
for(int i=2;i<=n;++i)
{
int mi=min(m,i);
f[i][0][0]=f[i-1][0][0]+dis[c[i-1]][c[i]];
for(int j=1;j<=mi;++j)
{
int C1=c[i-1],C2=d[i-1],C3=c[i],C4=d[i];
f[i][j][0]=min(
f[i-1][j][0]+dis[C1][C3],//C1->C3
f[i-1][j][1]+dis[C1][C3]*(1-k[i-1])+dis[C2][C3]*k[i-1]//C1->C3 & C2->C3
);
f[i][j][1]=min(
f[i-1][j-1][0]+dis[C1][C3]*(1-k[i])+dis[C1][C4]*k[i],//C1->C3 & C1->C4
f[i-1][j-1][1]+
dis[C1][C3]*(1-k[i-1])*(1-k[i])//C1->C3
+dis[C1][C4]*(1-k[i-1])*k[i]//C1->C4
+dis[C2][C3]*k[i-1]*(1-k[i])//C2->C3
+dis[C2][C4]*k[i-1]*k[i]//C2-C4
);
//形象直观QAQ
}
}
}
//懒得打方程了(逃
int main()
{
Init();
DP();
for(int i=0;i<=m;++i) ans=min(ans,min(f[n][i][0],f[n][i][1]));
printf("%.2lf
",ans);
return 0;
}
4 后记
判重边!
判重边!!
判重边!!!
再忘判重边我就女装!!!