[题解] [CF518D] Ilya and Escalator

题面

题解

期望dp入门题

设\(f[i][j]\)为到\(i\)时间有\(j\)个人上了电梯的概率, 我们可以得到转移方程

\[f[i][j]=\begin{cases}f[i-1][j]\cdot(1-p),&j=0\\f[i-1][j-1]\cdot p+f[i-1][j]\cdot(1-p),&j\in[1,n)\\f[i-1][n]+f[i-1][n-1]\cdot p,&j=n\end{cases}
\]

Code

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <vector>

#define itn int

#define reaD read

#define N 2005

using namespace std;

int n, t;

double f[N][N], p, ans; 

inline int read()

{

	int x = 0, w = 1; char c = getchar();

	while(c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }

	while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }

	return x * w;

}

int main()

{

	n = read(); scanf("%lf", &p); t = read();

	f[0][0] = 1;

	for(int i = 1; i <= t; i++)

	{

		f[i][0] = f[i - 1][0] * (1 - p);

		for(int j = 1; j < n; j++) f[i][j] = f[i - 1][j - 1] * p + f[i - 1][j] * (1 - p);

		f[i][n] = f[i - 1][n] + f[i - 1][n - 1] * p;

	}

	for(int i = 1; i <= n; i++) ans = (ans + (double) f[t][i] * i);

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

	return 0;

}

巴特西

[题解] [CF518D] Ilya and Escalator

题面

题解

Code

最新文章

热门文章