【HNOI2015】亚瑟王

题面

题解

考虑进行\(dp\)。

设\(f[i][j]\)表示前\(i\)张卡中有\(j\)张被触发的概率。

我们可以知道第\(i\)张卡不被触发的概率为\((1 - p_i) ^ {r - j}\)，因为一共会考虑\(r - j\)次，每次都没有触发。

所以被触发的概率为\(1 - (1 - p_i) ^ {r - j + 1}\)。

于是\(f[i][j] = f[i - 1][j] \times (1 - p_i) ^ {r - j} + f[i - 1][j - 1] \times (1 - (1 - p_i) ^ {r - j + 1})\)。

同样，设\(g[i][j]\)表示期望，类似地进行转移即可。

代码

#include<cstdio>

#include<cctype>

#define RG register

inline int read()

{

	int data = 0, w = 1; char ch = getchar();

	while(ch != '-' && (!isdigit(ch))) ch = getchar();

	if(ch == '-') w = -1, ch = getchar();

	while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();

	return data * w;

}

const int maxn(230), maxm(150);

double f[maxn][maxm], g[maxn][maxm], p[maxn], Pow[maxn][maxm];

int n, r, d[maxn], T;

int main()

{

	T = read(); f[0][0] = 1;

	while(T--)

	{

		n = read(), r = read();

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

		for(RG int i = 1; i <= n; i++) Pow[i][0] = 1, f[i][0] = g[i][0] = 0;

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

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

				f[i][j] = g[i][j] = 0, Pow[i][j] = Pow[i][j - 1] * (1 - p[i]);

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

			for(RG int j = 0; j <= r && j <= i; j++)

			{

				f[i][j] += f[i - 1][j] * Pow[i][r - j];

				g[i][j] += g[i - 1][j] * Pow[i][r - j];

				if(j) f[i][j] += f[i - 1][j - 1] * (1 - Pow[i][r - j + 1]),

					g[i][j] += (g[i - 1][j - 1] + d[i] * f[i - 1][j - 1]) *

						(1 - Pow[i][r - j + 1]);

			}

		double ans = 0;

		for(RG int i = 0; i <= r; i++) ans += g[n][i];

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

	}

	return 0;

}

巴特西

【HNOI2015】亚瑟王

题面

题解

代码

最新文章

热门文章