[Noip2016]换教室

一.前言

阿巴阿巴，好长的题面……题目链接

二.思路

看到数学期望就基本知道是DP了，然后状态也比较好想，属于最基础的那种 (f_{ij}) 表示前 i 个共提交了 j 次申请，但是涉及到申请的概率会交叉的问题，于是再加一维 0/1 表示这次是否尝试。

这里多嘴一句，一开始我还以为是总共只能成功 m 次，就把方程设成了 j 次成功……然后后面 0/1 那一维也是不可以设成成功的。（可以自己试试，反正我不行）

然后开始转移，对于当前情况，有(dis 表示教室之间的距离)

[f[i][j][0]= ext{min}(dp[i-1][j][0]+dis[c[i-1]][c[i]],\ dp[i-1][j][1]+(1.0-k[i-1])*dis[c[i-1]][c[i]]+k[i-1]*dis[d[i-1]][c[i]]) ]

就稍微解释……这次没有尝试，则上一次就要尝试 j 次，然后由上次没尝试和尝试了的成功与否转移。同理，

[dp[i][j][1]=min( dp[i-1][j-1][0]+k[i]*dis[c[i-1]][d[i]]+(1.0-k[i])*dis[c[i-1]][c[i]],\ dp[i-1][j-1][1]+ k[i-1]*k[i]*dis[d[i-1]][d[i]]+ (1.0-k[i-1])*k[i]*dis[c[i-1]][d[i]]+\ k[i-1]*(1.0-k[i])*dis[d[i-1]][c[i]]+ (1.0-k[i-1])*(1.0-k[i])*dis[c[i-1]][c[i]] ) ]

感觉有点过于长了……跟上面相同的思想我就不讲了。

最后是关于 dis ,看数据范围，教室数小于300 ，Floyd芜湖起飞~ （鬼知道我白给一个小时打了个什么奇怪算法呢~）

就酱。

三.CODE

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<fstream>
#include<cmath>
#include<cstring>
using namespace std;
#define m_for(i,a,b) for(int i=a;i<=b;++i)
int read(){
	char ch=getchar();
	int res=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())res=res*10+(ch-'0');
	return res*f;
}
const int MAXN=90005;
int n,m,v,e;
int c[MAXN],d[MAXN],dis[305][305];
double p[2005][2005][2],dp[2005][2005][2];
double k[MAXN];
int main(){
	memset(dis,127/3,sizeof(dis));
	n=read();m=read();v=read();e=read();
	m=min(m,n);
	m_for(i,1,n)c[i]=read();
	m_for(i,1,n)d[i]=read();
	m_for(i,1,n)scanf("%lf",&k[i]);
	m_for(i,1,v)dis[i][0]=dis[0][i]=dis[i][i]=0.0;
	for(int i=1,a,b,w;i<=e;++i){
		a=read();b=read();w=read();
		dis[a][b]=dis[b][a]=min(dis[b][a],w);
	}
	m_for(a,1,v)m_for(b,1,v)m_for(w,1,v)
	dis[b][w]=min(dis[b][w],dis[b][a]+dis[a][w]);
	m_for(i,1,n)m_for(j,0,m)dp[i][j][0]=dp[i][j][1]=MAXN*100.0;
	dp[1][1][1]=dp[1][0][0]=0.0;
	m_for(i,2,n){
		dp[i][0][0]=dp[i-1][0][0]+dis[c[i-1]][c[i]];
		for(int j=1;j<=i&&j<=m;++j){
			dp[i][j][1]=min(
			dp[i-1][j-1][0]+k[i]*dis[c[i-1]][d[i]]+(1.0-k[i])*dis[c[i-1]][c[i]],
			dp[i-1][j-1][1]+
			k[i-1]*k[i]*dis[d[i-1]][d[i]]+
			(1.0-k[i-1])*k[i]*dis[c[i-1]][d[i]]+
			k[i-1]*(1.0-k[i])*dis[d[i-1]][c[i]]+
			(1.0-k[i-1])*(1.0-k[i])*dis[c[i-1]][c[i]]
			);
			dp[i][j][0]=min(
			dp[i-1][j][0]+dis[c[i-1]][c[i]],
			dp[i-1][j][1]+(1.0-k[i-1])*dis[c[i-1]][c[i]]+k[i-1]*dis[d[i-1]][c[i]]
			);
		}
	}
	double ans=MAXN*100.0;
	for(int i=0;i<=m;++i){
		ans=min(ans,min(dp[n][i][0],dp[n][i][1]));
	}
	printf("%.2lf",ans);
	return 0;
}