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$次后再多走都和原来是一样的了),那么

移项得

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

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

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

代码

考虑到精度问题,代码中的s1s2是没有除的。

#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]);
	}
}