$\color{green}{洛谷P1850\ \ \ \ \ \ 换教室}$洛谷P1850      换教室

$\color{blue}{【题意】：}$【题意】：







$\color{blue}{【思路】：}$【思路】： 好冗长的题目啊……

这是一道$\color{red}{概率dp}$概率dp的题目。所谓的概率dp，大家可以直观的理解为用以计算概率的$dp$dp。它最大的特点是数学性强（即需要用到很多的数学公式）。

回到本题，我们根据$dp$dp的一般步骤来解答它。

第一步是检验本题是否可以$dp$dp解决。即检查本题是否具有无后效性等等的$dp$dp特性。此步很重要，但是因为篇幅，这里略去，仅仅告诉读者结论，本题可以用$dp$dp。

第二步是设计状态。我们记$dp[i][j][0/1]$dp[i][j][0/1]表示考虑到第$i$i个时间段，共换了$j$j次教室，其中如果第三维是$0$0，表示当前不需要换教室，是$1$1表示需要换教室；$f[i][j]$f[i][j]表示从$i$i到$j$j的最短路径，可以Floyd求出。

第三步是考虑转移。概率$dp$dp的又一大特性是它常常需要$\color{orange}{分类讨论}$分类讨论。

记$C1=c[i-1],C2=d[i-1],C3=c[i],C4=d[i]$C1=c[i−1],C2=d[i−1],C3=c[i],C4=d[i]，则

• $dp[i][j][0]=min(dp[i][j][0],min(dp[i-1][j][0]+f[C1][C3],dp[i-1][j][1]+f[C1][C3]\times (1-k[i-1])+f[C2][C3]\times k[i-1]))$dp[i][j][0]=min(dp[i][j][0],min(dp[i−1][j][0]+f[C1][C3],dp[i−1][j][1]+f[C1][C3]×(1−k[i−1])+f[C2][C3]×k[i−1]))
• $dp[i][j][1]=min(dp[i][j][1],min(dp[i-1][j-1][0]+f[C1][C3]\times (1-k[i])+f[C1][C4]\times k[i],dp[i-1][j-1][1]+f[C2][C4]\times k[i-1]\times k[i]+f[C2][C3]\times k[i-1]\times (1-k[i])+f[C1][C4]\times (1-k[i-1])\times k[i]+f[C1][C3]\times (1-k[i-1]) \times (1-k[i])))$dp[i][j][1]=min(dp[i][j][1],min(dp[i−1][j−1][0]+f[C1][C3]×(1−k[i])+f[C1][C4]×k[i],dp[i−1][j−1][1]+f[C2][C4]×k[i−1]×k[i]+f[C2][C3]×k[i−1]×(1−k[i])+f[C1][C4]×(1−k[i−1])×k[i]+f[C1][C3]×(1−k[i−1])×(1−k[i])))

以$dp[i][j][0]$dp[i][j][0]的转移为例。有一种方案是第$i-1$i−1秒不换教室，两次都不换教室，则答案为$dp[i-1][j][0]+f[C1][C3]$dp[i−1][j][0]+f[C1][C3]。令一种方案为第$i-1$i−1秒换教室，则又有两种方案：一是从$c[i-1]$c[i−1]到$d[i-1]$d[i−1]成功，则贡献为$f[C2][C3]\times k[i-1]$f[C2][C3]×k[i−1]；二是从$cf[i-1]$cf[i−1]到$d[i-1]$d[i−1]不成功，既然从$c[i-1]$c[i−1]到$d[i-1]$d[i−1]成功的概率为$k[i-1]$k[i−1]，那么不成功的概率为$1-k[i-1]$1−k[i−1]，因为两件事不同时发生，则总贡献为$f[C1][C3]\times (1-k[i-1])$f[C1][C3]×(1−k[i−1])。所以总答案为$dp[i-1][j][1]+f[C1][C3] \times (1-k[i-1])+f[C2][C3]\times k[i-1]$dp[i−1][j][1]+f[C1][C3]×(1−k[i−1])+f[C2][C3]×k[i−1]。$dp[i][j][0]$dp[i][j][0]就在两种答案间取较小值即可。

$\color{blue}{【代码】：}$【代码】：

int f[310][310],n,m,v,e;
double dp[2010][2010][3];
//f[i][j]:从i到j的最短路径，可以Floyd求出 
//dp[i][j][1]:考虑到第i个时间段，共换了j次教室，当前也换教室的答案
//dp[i][j][0]:考虑到第i个时间段，共换了j次教室，当前不换教室的答案
inline void floyd_algorithm(){
	for(int k=1;k<=v;k++)
		for(int i=1;i<=v;i++)
			if (i!=k)
				for(int j=1;j<=v;j++)
					f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
double k[2010],ans;
int c[2010],d[2010];
const double inf=1e17;
int main(){
	freopen("t1.in","r",stdin);
	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]);
	memset(f,63,sizeof(f));
	for(int i=1;i<=e;i++){
		register int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		f[u][v]=f[v][u]=min(f[u][v],w);
	}
	floyd_algorithm();ans=inf;
	for(int i=1;i<=v;i++)
		f[i][i]=f[i][0]=f[0][i]=0;
	for(int i=0;i<=n;i++)
		for(int j=0;j<=m;j++)
			dp[i][j][0]=dp[i][j][1]=inf;
	dp[1][0][0]=dp[1][1][1]=0;
	for(int i=2;i<=n;i++){
		int C1=c[i-1],C2=d[i-1],C3=c[i],C4=d[i];
		dp[i][0][0]=dp[i-1][0][0]+f[C1][C3];
		for(int j=1;j<=min(i,m);j++){
			dp[i][j][0]=min(dp[i][j][0],min(dp[i-1][j][0]+f[C1][C3],dp[i-1][j][1]+f[C1][C3]*(1-k[i-1])+f[C2][C3]*k[i-1]));
			dp[i][j][1]=min(dp[i][j][1],min(dp[i-1][j-1][0]+f[C1][C3]*(1-k[i])+f[C1][C4]*k[i],dp[i-1][j-1][1]+f[C2][C4]*k[i-1]*k[i]+f[C2][C3]*k[i-1]*(1-k[i])+f[C1][C4]*(1-k[i-1])*k[i]+f[C1][C3]*(1-k[i-1])*(1-k[i])));
		}
	}
	for(int i=0;i<=m;i++)
		ans=min(ans,min(dp[n][i][0],dp[n][i][1]));
	printf("%.2lf",ans);
	return 0;
}

• 点赞
• 收藏
• 分享
• • 文章举报

ZHUYINGYE_123456 发布了78 篇原创文章 · 获赞 4 · 访问量 1227 私信 关注