Description

题目链接:Luogu

Solution

这题结合了DP和概率与期望，其实只要稍微知道什么是期望就可以了，

状态的构造很关键，\(F[i][j][0/1]\)表示已经到第\(i\)个课程，之前用了\(j\)个申请机会，且当前课程是(1)否(0)申请

然后就容易想到转移方程，

\(F_{i,j,0}=min\{F_{i-1,j,0}+dis(c_{i-1},c_i),F_{i-1,j,1}+dis(c_{i-1},c_i)*(1-p_{i-1})+dis(d_{i-1},c_i)*p_{i-1}\}\)

方程看起来复杂但仔细分析会会发现其实很裸

Code

#include <cstdio>

#include <algorithm>

#include <cstring>

#define db double

#define N 2010

using namespace std; 

int n,m,V,E,c[N],d[N],g[320][320];

db p[N],f[N][N][2],Ans;

inline int read() {

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch = getchar();}

	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch = getchar();}

	return x*f;

}

inline void Init(){

	n=read(),m=read(),V=read(),E=read();

	for(int i=1;i<=n;++i) c[i]=read();

	for(int i=1;i<=n;++i) d[i]=read();

	for(int i=1;i<=n;++i) scanf("%lf",&p[i]);

	memset(g,127/2,sizeof(g));

	for(int i=1;i<=E;++i){

		int u=read(),v=read(),w=read();

		g[u][v]=min(g[u][v],w);

		g[v][u]=g[u][v];

	}

	for(int k=1;k<=V;++k)

		for(int i=1;i<=V;++i)

			for(int j=1;j<=V;++j)

				g[i][j]=min(g[i][j],g[i][k]+g[k][j]);

	for(int i=1;i<=V;++i) g[i][i]=0;

}

int main() {

	Init();

	for(int i=1;i<=n;++i)for(int j=0;j<=m;++j)f[i][j][0]=f[i][j][1]=1e9;

	f[1][0][0]=f[1][1][1]=0;

	for(int i=2;i<=n;++i){

		int lim=max(i,m);

		for(int j=0;j<=lim;++j){

			f[i][j][0]=min(f[i-1][j][0]+g[c[i-1]][c[i]],f[i-1][j][1]+g[c[i-1]][c[i]]*(1.0-p[i-1])+g[d[i-1]][c[i]]*p[i-1]);

			if(j<1) continue; 

			db tmp=f[i-1][j-1][1]+g[c[i-1]][c[i]]*(1.0-p[i-1])*(1.0-p[i])+g[d[i-1]][d[i]]*p[i-1]*p[i];

			tmp+=g[c[i-1]][d[i]]*(1.0-p[i-1])*p[i]+g[d[i-1]][c[i]]*p[i-1]*(1.0-p[i]);

			f[i][j][1]=min(tmp,f[i-1][j-1][0]+g[c[i-1]][c[i]]*(1.0-p[i])+g[c[i-1]][d[i]]*p[i]);

		}

	}

	Ans=1e9;

	for(int i=0;i<=m;++i) Ans=min(Ans,min(f[n][i][0],f[n][i][1]));

	printf("%.2lf\n",Ans);

	return 0;

}