[题解] [CF518D] Ilya and Escalator

题面

题解

期望dp入门题

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

[f[i][j]=egin{cases}f[i-1][j]cdot(1-p),&j=0\f[i-1][j-1]cdot p+f[i-1][j]cdot(1-p),&jin[1,n)\f[i-1][n]+f[i-1][n-1]cdot p,&j=nend{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
", ans); 
	return 0;
}