NOIP2016 提高组 换教室

NOIP2016 提高组 换教室

非常简单的一道期望 dp，但是自己做的时候严重想复杂导致做了3天……

算法一

容易发现任意两次课之间转移的期望代价只和当前起终点的状态有关，因此每次转移可以独立出来了。现在想怎么算这个期望。

一个结论：期望的计算:如果概率为 \(k\) 的代价为 \(w_1\),概率为 \((1-k)\) 的代价为 \(w_2\)，那么期望就是概率乘代价，即 \(k \times w1+(1-k) \times w2\)。（来自 题解 P1850 【换教室】- by qwaszx ）

爆搜每个位置申请或不申请，时间复杂度是 \(O(\binom{n}{m})\)。实现的比较好所以得了 80pts。

算法二

改成 dp，记 \(f_{i, j, 0/1}\) 表示 \(1 \sim i\)，用了 \(j\) 次申请，第 \(i\) 申请 / 不申请，最小期望代价和。转移是显然的，分讨一下就好。

#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=(r);++i)
#define G(i,r,l) for(int i(r);i>=(l);--i)
using namespace std;
using ll = long long;
using db = double; 
char buf[100], *p1 = buf, *p2 = buf;
inline int gc(){
	return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, 100, stdin), p1 == p2) ? EOF : *p1++;
}
inline db rd(){
	db x = 0; char ch; bool f = 1;
	while(!isdigit(ch = gc())) f ^= (ch == '-');
	do x = x * 10 + (ch ^ 48); while(isdigit(ch = gc()));
	if(ch == '.'){
		db k = 0.1;
		while(isdigit(ch = gc())) x += (ch ^ 48) * k, k /= 10;
	}
	return f ? x : -x;
}
const int N = 2005;
const int M = 305;
const int inf = 0x3f3f3f3f;
int dis[M][M];
int a[N], b[N];
db k[N], f[N][N][2];
int n, m, v, e;
void floyed(){
	F(k, 1, v) F(i, 1, v) F(j, 1, v) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
void Min(double &x, double y){
	(x > y) &&(x = y);
}
double solve(){
	F(i, 0, n) F(j, 0, m) f[i][j][0] = f[i][j][1] = 1e9;
	f[1][1][1] = f[1][0][0] = 0;
	F(i, 2, n){
		F(j, 0, m){
			f[i][j][0] = min(f[i - 1][j][0] + dis[a[i - 1]][a[i]], f[i - 1][j][1] + dis[a[i - 1]][a[i]] * (1 - k[i - 1]) + dis[b[i - 1]][a[i]] * k[i - 1]);
			if(j){
				f[i][j][1] = min(f[i - 1][j - 1][0] + dis[a[i - 1]][a[i]] * (1 - k[i]) + dis[a[i - 1]][b[i]] * k[i],
								 f[i - 1][j - 1][1] + dis[a[i - 1]][a[i]] * (1 - k[i - 1]) * (1 - k[i])
								 					+ dis[b[i - 1]][a[i]] * k[i - 1] * (1 - k[i])
													+ dis[a[i - 1]][b[i]] * (1 - k[i - 1]) * k[i]
													+ dis[b[i - 1]][b[i]] * k[i - 1] * k[i]
				);
			}
		}
	}
	db ans = 1e9;
	F(i, 0, m) Min(ans, f[n][i][0]), Min(ans, f[n][i][1]);
	return ans;
}
signed main(){
	n = rd(), m = rd(), v = rd(), e = rd();
	F(i, 1, n) a[i] = rd();
	F(i, 1, n) b[i] = rd();
	F(i, 1, n) k[i] = rd();
	F(i, 1, v) F(j, 1, v) dis[i][j] = (i == j) ? 0 : inf;
	F(i, 1, e){
		int x = rd(), y = rd(), z = rd();	
		dis[x][y] = min(dis[x][y], z);
		dis[y][x] = dis[x][y];
	}
	floyed();
	printf("%.2lf", solve());
	return fflush(0), 0;
}

总结

本题主要困住我的地方在于我很自然地把贡献拆成了当前点申请和不申请两部分去分别看待，导致每步转移要四个贡献合起来，而不是两个，搞得非常复杂，因此暴力都分析了很长的事件。对期望的认识还不够。