题意简述

• $n$ 个人排成一列。每秒有 $p$ 的概率，队伍的第一个人走上电梯。

• 求 $t$ 秒后已经走上电梯人数的期望值。

• $1\leq n,t\leq 2000$，$0\leq p\leq 1$

题目分析

动态规划，定义状态 $f_{i,j}$ 表示前 $i$ 个人 $j$ 秒内走上电梯人数的期望值。

分类讨论第 $j$ 秒第一个人是否上电梯：

• 对于 $p$ 的概率，第一个人上了电梯，贡献为 $(f_{i-1,j-1}+1)\times p$；

• 对于 $1-p$ 的概率，第一个人没有走上电梯，贡献为 $f_{i,j-1}\times(1-p)$。

最终答案为 $f_{n,t}$，时间复杂度 $\Theta(nt)$。

代码

#include <bits/stdc++.h>
using namespace std;
int n,t; double p,f[2001][2001];
//f[i][j]: 前i个人j秒期望人数 
int main(){
	scanf("%d%lf%d",&n,&p,&t);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=t;j++)
			f[i][j]=(f[i-1][j-1]+1)*p+f[i][j-1]*(1-p);
	printf("%.8lf\n",f[n][t]);
    return 0;
}