题面

Sol

方法一

直接状压就好了

# include <bits/stdc++.h>

# define RG register

# define IL inline

# define Fill(a, b) memset(a, b, sizeof(a))

using namespace std;

typedef long long ll;

int n;

double p[21], f[1 << 20];

int main(RG int argc, RG char *argv[]){

	while(scanf("%d", &n) != EOF){

		for(RG int i = 1; i <= n; ++i) scanf("%lf", &p[i]);

		RG int S = 1 << n; Fill(f, 0);

		for(RG int i = S - 2; ~i; --i){

			RG double s = 1.0;

			for(RG int j = 1; j <= n; ++j) if(~i & (1 << (j - 1))) s -= p[j];

			s = 1.0 - s, f[i] = 1.0 / s;

			for(RG int j = 1; j <= n; ++j)

				if(~i & (1 << (j - 1))) f[i] += p[j] * f[i | (1 << (j - 1))] / s;

		}

		printf("%.6lf\n", f[0]);

	}

    return 0;

}

方法二

方法一实在太水了，显然不是重点

下面介绍一种容斥方法

min-max容斥

\(E[max(S)]=\sum(-1)^{k+1}E[min(S')]\)

其中集合\(S'\subseteq S\)，\(k=|S'|\)

\(max(S)\)指的是这个集合内最后出现的元素

\(min(S)\)指的是这个集合内最先出现的元素

\(E\)表示期望第几步出现

具体到这个题

就是要求\(E[max(\)全集\()]\)

\(E[min(S')]\)就是指\(S'\)任意出现一个的期望步数

举例：

每步出现\(x_i\)的概率\(p_i\)

\(min\{x_1, x_2, x_3 \}\)的概率就是\(p_1+p_2+p_3\)

期望步数就是\(\frac{1}{p_1+p_2+p_3}\)

然后就容斥一下这个题

# include <bits/stdc++.h>

# define RG register

# define IL inline

# define Fill(a, b) memset(a, b, sizeof(a))

using namespace std;

typedef long long ll;

int n;

double p[21], ans;

IL void Dfs(RG int x, RG double E, RG int op){

	if(x > n){

		if(E > 1e-7) ans += 1.0 * op / E;

		return;

	}

	Dfs(x + 1, E, op);

	Dfs(x + 1, E + p[x], -op);

}

int main(RG int argc, RG char *argv[]){

	while(scanf("%d", &n) != EOF){

		for(RG int i = 1; i <= n; ++i) scanf("%lf", &p[i]);

		ans = 0, Dfs(1, 0, -1);

		printf("%.6lf\n", ans);

	}

    return 0;

}

巴特西

HDU4336：Card Collector(min-max容斥)

题面

Sol

方法一

方法二

min-max容斥

最新文章

热门文章