[NOIP提高组2016]换教室 解题报告

题目大意：

牛牛（谢*宇）上大学了！但是他要选课——有两门共2n节课分布在n个时间段上…太复杂了！不如说：

牛牛要上n节课，每节课有两个去处。学校已经给他安排好了这n节课的教室的编号，即c数组。但是他可以申请换课，即把第ci节课换到di去，d数组就是换课后的教室编号。申请换课不一定能通过，成功的概率用k数组存。对于第bi节课，换课成功的概率是ki。而且每节课换成功的概率之间是相互独立的。

图如下：

因为每一节课可能在不同的教室上，所以每节课下了之后牛牛要赶到另一个教室去上课。牛牛所在的大学有v个教室，e条道路，且是双向的，每条路由于距离与拥堵程度耗费的体力不同，所以牛牛想找到一种申请课的方案，使得体力的消耗期望值最小。

读入：

第一行四个整数n,m,v,e。 n表示这个学期内的时间段的数量（就是有多少节课）；m表示牛牛最多可以申请更换多少节课程的教室（最多换课数）；v表示牛牛学校里教室的数量（图有多少点）；e表示牛牛的学校里道路的数量（图有多少边）。

第二行 n 个正整数，第 i（1≤i≤n）个正整数表示 ci，即第 i 个时间段牛牛被安排上课的教室；保证 1≤ci≤v。（被安排的）

第三行 n 个正整数，第 i（1≤i≤n）个正整数表示 di，即第 i 个时间段另一间上同样课程的教室；保证 1≤di≤v。（可以换的课的教室）

第四行 n 个实数，第 i（1≤i≤n）个实数表示 ki，即牛牛申请在第 i 个时间段更换教室获得通过的概率。保证 0≤ki≤1。（即第i节课换课成功的概率）

接下来 e 行，每行三个正整数 aj,bj,wj，表示有一条双向道路连接教室 aj,bj ,通过这条道路需要耗费的体力值是wj；保证 1≤aj,bj≤v，1≤wj≤100。（建图了）

保证1≤n≤2000，0≤m≤2000，1≤v≤300，0≤e≤90000。保证通过学校里的道路，从任何一间教室出发，都能到达其他所有的教室。保证输入的实数最多包含3位小数。

输出：

输出一行，包含一个实数，四舍五入精确到小数点后恰好2位，表示答案。你的输出必须和标准输出完全一样才算正确。测试数据保证四舍五入后的答案和准确答案的差的绝对值不大于 4×10^(-3)。（如果你不知道什么是浮点误差，这段话可以理解为：对于大多数的算法，你可以正常地使用浮点数类型而不用对它进行特殊的处理）

样例输入：

3 2 3 3
2 1 2
1 2 1
0.8 0.2 0.5 
1 2 5
1 3 3
2 3 1

样例输出：

2.80

---

终于搞定了题目大意！(题面太长了⑧)

考试时我看到这题先打了个爆搜（源码已丢失），然后样例都没过＝＝

后来想了想dp，发现可以的！用三维f[N][N][2]数组存下状态，第一维i表示当前这节课的教室，第二维j表示从第一节课到第min(i,m)节课的换课数（因为最多只能换m节课），第三维0表示不换，1表示换。这样一来，状态转移方程就可表示为：(这个零怎么长得有点像o)

f（i,j,0）(这节课不换)=min(上节课也不换+上节课的教室到这节课教室需要的体力，上节课换+成功的概率×如果成功需要的体力+不成功的概率×不成功需要的体力)，即：
f[i][j][0]=min(f[i-1][j][0]+dis[c[i-1]][c[i]],f[i-1][j][1]+(1-k[i-1])*dis[c[i-1]][c[i]]+k[i-1]*dis[d[i-1]][c[i]]);

f（i,j,1）（这节课换）=min(上节课不换+这节课换成功的概率×上节课教室到这节课教室的体力+这节课没换成的概率×上节课教室到这节课教室的体力，上节课换+上节课换成功×这节课换成功+上节课没换成×这节课换成功+上节课换成功×这节课没换成+两节课都没换成)（这里偷个懒）
f[i][j][1]=min(f[i-1][j-1][0]+k[i]*dis[c[i-1]][d[i]]+(1-k[i])*dis[c[i-1]][c[i]],f[i-1][j-1][1]+k[i-1]*k[i]*dis[d[i-1]][d[i]]+(1-k[i-1])*k[i]*dis[c[i-1]][d[i]]+k[i-1]*(1-k[i])*dis[d[i-1]][c[i]]+(1-k[i-1])*(1-k[i])*dis[c[i-1]][c[i]]);
（j-1是因为这节课申请了所以往前找时要减1。）

既然有了状态转移方程，再看下v的数据范围——[0,300]，对Floyd来说是可以承受的！所以用Floyd先预处理每间教室之间最省体力的走法，之后直接dp就行了。

放代码！

#pragma GCC optimize(2)//手动吸氧(其实没啥用)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 2005,V = 305,INF = 0x7f;//0x7f是memset里double类型的极大值
int n,m,v,e;
int c[N],d[N];
double k[N],dis[V][V],f[N][N][2];//f：当前教室/申请换的教室数/当前是否申请 
inline int qread(){//快读
	int x=0,w=1;
	char ch=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+(ch-'0');
		ch=getchar();
	}
	return x*w;
}

int main(){
	memset(dis,INF,sizeof(dis));//初始化
	memset(f,INF,sizeof(f));//初始化
    f[1][0][0]=f[1][1][1]=0;//第一节课换不换都是起点，因此初始化为0
	n=qread(),m=qread(),v=qread(),e=qread();
	for(int i=1;i<=v;++i)dis[i][i]=0;//每间教室到自己距离为0
	for(int i=1;i<=n;++i)c[i]=qread();
	for(int i=1;i<=n;++i)d[i]=qread();
	for(int i=1;i<=n;++i)scanf("%lf",&k[i]);//读入换课成功的概率
	for(int i=1;i<=e;++i){
		int x=qread(),y=qread(),w=qread();//读入第x到y教室的体力
		dis[x][y]=dis[y][x]=min(dis[x][y],(double)w);
	}for(int h=1;h<=v;++h)//Floyd处理所有教室之间最小体力
		for(int i=1;i<=v;++i)
			for(int j=1;j<=v;++j)
	dis[i][j]=min(dis[i][j],dis[i][h]+dis[h][j]);
	for(int i=2;i<=n;++i){//i为当前教室，i=1时啥都是0是起点所以从2开始dp 
		f[i][0][0]=f[i-1][0][0]+dis[c[i-1]][c[i]];//不申请换课那就按安排好的走 
		for(int j=1;j<=min(i,m);++j){//j为申请换的教室数量，第三维0表示没申请，1表示申请了  
			f[i][j][0]=min(f[i-1][j][0]+dis[c[i-1]][c[i]],f[i-1][j][1]+(1-k[i-1])*dis[c[i-1]][c[i]]+k[i-1]*dis[d[i-1]][c[i]]);//第i节课不申请换 
			f[i][j][1]=min(f[i-1][j-1][0]+k[i]*dis[c[i-1]][d[i]]+(1-k[i])*dis[c[i-1]][c[i]],f[i-1][j-1][1]+k[i-1]*k[i]*dis[d[i-1]][d[i]]+(1-k[i-1])*k[i]*dis[c[i-1]][d[i]]+k[i-1]*(1-k[i])*dis[d[i-1]][c[i]]+(1-k[i-1])*(1-k[i])*dis[c[i-1]][c[i]]);//第i节课申请换 
		}
	}double ans=f[n][0][0];//记录最终答案，初始化为一节都不换的值
	for(int i=1;i<=m;++i)ans=min(ans,min(f[n][i][0],f[n][i][1]));//找最优解
	printf("%.2lf\n",ans);//输出
	return 0;
}

终于结束~

另请参阅：
我的洛谷博客