夏晓光(loveJY)的博客

IOI2020集训队作业

233补作业qwq

• n 个点的有向完全图。
• $i \to j$ 的边每天出现的概率均为 $p_{i,j}$​，若$i = j$，有 $p_{i,j} = 1$。
• 每天选择一条存在的出边走过去。
• 求最优策略下从 $1$ 到 $n$ 的期望天数。
• $n \le 10^3$。

设$E_x$为从x到n的最小天数

$E_x=\sum_iE_i*p_{x,i}\prod_{j=1}^{i-1}(1-p_{x,j})$

所以我们可以每次找到走到n期望天数最小的然后用他去更新新的答案,$E_x$要注意我们还没有算停留在原地的概率

除掉$1-\prod_{p}$就是答案了

#include<iostream>
#include<cstdio>
#include<algorithm>
#define R register
#define ll long long
const int MAXN = 1e3 + 7;
int n, vis[MAXN], a[MAXN];
double p[MAXN][MAXN], d[MAXN], sum[MAXN], pr[MAXN];


int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		int nw = 0;
		sum[i] = pr[i] = 1.0;
		for(int j = 1; j <= n; ++j) {
			scanf("%d", &nw);
			p[i][j] = nw * 0.01L;
            //算概率
		}
	}
	vis[n] = 1;
	a[1] = n;//第一个点qwq
	d[0] = 1e18;
	for(int i = 2; i <= n; ++i) {
		for(int j = 1; j <= n; ++j) {
			if(vis[j])continue;
			sum[j] += d[a[i - 1]] * p[j][a[i - 1]] * pr[j];
			pr[j] *= (1 - p[j][a[i - 1]]);
			d[j] = sum[j] / (1 - pr[j]);
            //sum没问题
            //pr是之前没有到的概率
            //d是更新这个点答案,注意除以qwq
		}
		int pos = 0;
		for(int j = 1; j <= n; ++j) {
			if(!vis[j] && d[pos] > d[j])pos = j;//选择一个概率最大的qwq
		}
		vis[pos] = 1;
		a[i] = pos;
	}
	printf("%.10lf\n", d[1]);
	return 0;
}