LightOJ1395 | UVA12411 A Dangerous Maze (II)

01 June 2019 | duanyll | Tags: OI 题解 概率DP

题意

你在一个迷宫里，有$n$条路，你每次选择一条，花费$a_i$时间尝试走这条路，一些路会把你送到出口，另一些路会让你回到起点（已知），你不会走最近$k$次走过的路口，问走出迷宫需要时间的期望，如果不能走出迷宫，输出$-1$

分析

首先，在期望的条件下，具体每个门的耗时是不重要的，我们只需知道平均每扇能走出去的门的耗时是$\bar{s_1}$，不能走出去的门的耗时是$\bar{s_2}$，出口有$a$个，不是出口的有$b$个。定义$dp[i]$代表走了$i$次后走出去的期望，$dp[k]$代表最终走出来的期望（达到$k$次后再多走都和原来是一样的了），那么

\[dp[k] = \frac{a\bar{s_1} + (b-k)(\bar{s_2} + dp[k])}{n-k}\]

移项得

\[dp[k] = \bar{s_1} + \frac{(b-k)\bar{s_2}}{a}\]

对于$b>k$的情况，则令$k=b,dp[k]=\bar{s_1}$

再考虑不到$k$步就走出去了的情况

\[dp[i] = \frac{a\bar{s_1} + (b-i)(\bar{s_2} + dp[i+1])}{n-i}\]

最后答案就是$dp[0]$

代码

考虑到精度问题，代码中的s1、s2是没有除的。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 110;

double dp[MAXN];

int main() {
	int tcnt;
	cin >> tcnt;
	for (int T = 1; T <= tcnt; T++) {
		int n, k;
		cin >> n >> k;
		double s1 = 0, s2 = 0;
		int a = 0, b = 0;
		for (int i = 1; i <= n; i++) {
			double x;
			cin >> x;
			if (x > 0) {
				s1 += x;
				a++;
			} else {
				s2 -= x;
				b++; 
			}
		}
		if (b == n) {
			printf("Case %d: %.3lf\n", T, -1.0);
			continue;
		}
		if (k >= b) {
			k = b;
			dp[k] = s1 / a;
		} else {
			dp[k] = s1 / a + ((b - k) * s2 / b) / a;
		}
		for (int i = k - 1; i >= 0; i--) {
			dp[i] = (s1 + (b - i) * (s2 / b + dp[i + 1])) / (n - i);
		}
		printf("Case %d: %.3lf\n", T, dp[0]);
	}
}