【noip2016】换教室 题解

题目大意

  给出一幅 v 个点的无向图，表示教室及其连边。
  有 n 个时刻，每个时刻正常要到教室 c[i] 上课，如果该时刻有申请更换，则到教室 d[i] 上课。
  你只能在一切开始之前提交申请，且最多申请换 m 个时刻。第 i 个时刻申请成功的概率为 k[i]。
  求移动路程的期望最小值。
  n,m<=2000， v<=300

对于那副图的处理

  Floyd求出任意两点最短路，然后那幅图就没用了。

dp

  一开始我设的是 $f[i][j][0/1]$ 表示，到第 i 个时刻，已经申请了 j 次，第 i 个时刻是否换教室，的最小期望。
  这样推一推就发现是错的了。因为申请与否跟最终换不换教室是两回事。

  所以应该设 $f[i][j][0/1]$ 表示，到第 i 个时刻，已经申请了 j 次，第 i 个时刻是否申请，的最小期望。
  然后这样就相当于 i-1 的 0 和 1 两个点，转移到 i 的 0 和 1 两个点。总共四种转移，每种转移的期望代价就考虑一下多大概率是从 c[i-1] 来、多大概率从 d[i-1] 来，多大概率到 c[i] 去、多大概率到 d[i] 去，然后相应地乘上最短路即可。

告诉我v、n打反的不止我一个

  T^T
  QAQ

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;

const int maxn=2005, maxv=305;
const LL inf=1e11;

int n,m,v,e,rm[maxn][2];
double k[maxn];

int dis[maxv][maxv];
void Floyd()
{
	fo(k,1,v)
		fo(i,1,v) if (i!=k && dis[i][k]<dis[0][0])
			fo(j,1,v) if (j!=i && j!=k && dis[k][j]<dis[0][0] && dis[i][j]>dis[i][k]+dis[k][j])
				dis[i][j]=dis[i][k]+dis[k][j];
}

double Min(double x,double y)
{
	if (x>inf && y>inf) return inf;
	if (x>inf) return y;
	if (y>inf) return x;
	if (x<y) return x; else return y;
}

double f[maxn][maxn][2];
int main()
{
	freopen("classroom.in","r",stdin);
	freopen("classroom.out","w",stdout);
	
	scanf("%d %d %d %d",&n,&m,&v,&e);
	fo(i,1,n) scanf("%d",&rm[i][0]);
	fo(i,1,n) scanf("%d",&rm[i][1]);
	fo(i,1,n) scanf("%lf",&k[i]);
	
	memset(dis,127,sizeof(dis));
	fo(i,1,e)
	{
		int x,y,w;
		scanf("%d %d %d",&x,&y,&w);
		dis[x][y]=min(dis[x][y],w);
		dis[y][x]=min(dis[y][x],w);
	}
	fo(i,1,v) dis[i][i]=0;
	Floyd();
	
	fo(i,1,n)
		fo(j,0,m)
			fo(c,0,1) f[i][j][c]=inf;
	f[1][0][0]=f[1][1][1]=0;
	fo(i,2,n)
		fo(j,0,m)
			fo(c,0,1)
			{
				double t=k[i-1]*dis[rm[i-1][1]][rm[i][0]]+(1-k[i-1])*dis[rm[i-1][0]][rm[i][0]];
				f[i][j][0]=Min(f[i-1][j][0]+dis[rm[i-1][0]][rm[i][0]],f[i-1][j][1]+t);
				if (j)
				{
					double t1=k[i]*dis[rm[i-1][0]][rm[i][1]]+(1-k[i])*dis[rm[i-1][0]][rm[i][0]];
					t=k[i-1]*k[i]*dis[rm[i-1][1]][rm[i][1]]+(1-k[i-1])*k[i]*dis[rm[i-1][0]][rm[i][1]];
					t+=k[i-1]*(1-k[i])*dis[rm[i-1][1]][rm[i][0]]+(1-k[i-1])*(1-k[i])*dis[rm[i-1][0]][rm[i][0]];
					f[i][j][1]=Min(f[i-1][j-1][0]+t1,f[i-1][j-1][1]+t);
				}
			}
	
	double ans=inf;
	fo(j,0,m) ans=min(ans,Min(f[n][j][0],f[n][j][1]));
	
	printf("%.2f\n",ans);
}