洛谷P1850 换教室 题解

天哪这道题真的是神仙。。。

orz出题人

能出这种dp转移都写吐血的题目真的tql

description:

给出n个时间段，可申请m次换课，每次换课可申请从 $c\left[i\right]$c[i]换到 $d\left[i\right]$d[i],并有 $k\left[i\right]$k[i]的概率换课成功，每个教室有间距，问路程期望的最小值。

solution：

首先这就是一道期望dp题。

说到期望，

https://45475.blog.luogu.org/mathematical-expectation

这篇日报大概会给你不少的启发。

考虑Dp

设 $f\left[i\right]\left[j\right]\left[0/1\right]$f[i][j][0/1]表示前i节课申请了j次，第i次是否申请的期望最优解。

则：

$f\left[i\right]\left[j\right]\left[0\right]=\min \left(f\right[i\left]\right[j\left]\right[0],f[i-1\left]\right[j\left]\right[0]+a[c[i-1]\left]\right[c\left[i\right]],f[i-1\left]\right[j\left]\right[1]+(1-k[i-1])\ast a[c[i-1]\left]\right[c\left[i\right]]+k[i-1]\ast a[d[i-1]\left]\right[c\left[i\right]\left]\right)$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$c的规定走就行了。

• 上一次申请换课了：

1、通过了，那么就从上一次的d到现在的c

2、没通过，跟上一次没申请一样

$f\left[i\right]\left[j\right]\left[1\right]=\min \left(f\right[i\left]\right[j\left]\right[1],f[i-1\left]\right[j-1\left]\right[0]+k[i]\ast a[c[i-1]\left]\right[d\left[i\right]]+(1-k\left[i\right])\ast a[c[i-1]\left]\right[c\left[i\right]],f[i-1\left]\right[j-1\left]\right[1]+k[i-1]\ast k[i]\ast a[d[i-1]\left]\right[d\left[i\right]]+k[i-1]\ast (1-k\left[i\right])\ast a[d[i-1]\left]\right[c\left[i\right]]+(1-k[i-1])\ast k[i]\ast a[c[i-1]\left]\right[d\left[i\right]]+(1-k[i-1])\ast (1-k\left[i\right])\ast a[c[i-1]\left]\right[c\left[i\right]\left]\right)$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\left]\right)\times c[i-1],k[i-1]\ast d[i-1]$(1−k[i−1])×c[i−1],k[i−1]∗d[i−1]

这次申请的两种情况：

$(1-k[i\left]\right)\times c\left[i\right],k\left[i\right]\ast d\left[i\right]$(1−k[i])×c[i],k[i]∗d[i]

现在，只要两两组合即可，共有 $2\times 2=4$2×2=4种来源。

a数组是什么？

这是两点间距离数组，观察到教室数较少，Floyd求出即可

code：

#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;
}