code1083，Codeforces518 D. Ilya and Escalator

2023-10-21 阅读 28 评论 0

摘要：傳送門：>Here< 題意：有n個人排隊做電梯，每個人必須等前面的人全部上了以后才能上。對于每秒鐘，有p的概率選擇上電梯，(1-p)的概率選擇不上電梯。現在問t秒期望多少人上電梯解題思路： code1083、　　期望DP。　　$f[i][j]$表

傳送門：>Here<

題意：有n個人排隊做電梯，每個人必須等前面的人全部上了以后才能上。對于每秒鐘，有p的概率選擇上電梯，(1-p)的概率選擇不上電梯。現在問t秒期望多少人上電梯

解題思路：

code1083、　　期望DP。

　　$f[i][j]$表示第i秒上了j個人的概率。

　　$f[1][1] = p, f[1][0] = (1 - p)$，并且$f[i][0]$都需要初始化。（$* (1 - p)$）

　　這題好像和普通的期望DP不太一樣啊，因為f數組設的是概率而不是期望。這樣設的話答案就應該是$\sum\limits_{i = 0}^{Min(n, t)}f[t][i] * i$

code1515？　　考慮如何轉移：

　　第i秒的時候不上人：$ f[i-1][j] * (1 - p) $

　　第i秒的時候上人：$ f[i-1][j-1] * p $

　　因此對于一般情況：$$f[i][j] = f[i-1][j] * (1 - p) + f[i-1][j-1] * p$$

　　另外，總共就n個人，如果$t > n$就需要特判了：$$f[i][n] = f[i-1][n] + f[i-1][n-1]*p$$

Code

　　還是邊界條件！對于$f[i][j]$，由于每秒最多上一個人，所以$j$是不可能大于$i$的，要特判一下。

/*By QiXingzhi*/
#include <cstdio>
#include <queue>
#define  r  read()
#define  Max(a,b)  (((a)>(b)) ? (a) : (b))
#define  Min(a,b)  (((a)<(b)) ? (a) : (b))
using namespace std;
typedef long long ll;
const int N = 2010;
const int INF = 1061109567;
inline int read(){int x = 0; int w = 1; register int c = getchar();while(c ^ '-' && (c < '0' || c > '9')) c = getchar();if(c == '-') w = -1, c = getchar();while(c >= '0' && c <= '9') x = (x << 3) +(x << 1) + c - '0', c = getchar();return x * w;
}
int n,t;
double p,f[N][N],cur,ans;
int main(){
//    freopen(".in", "r", stdin);scanf("%d %lf %d",&n,&p,&t);f[1][1] = p;f[1][0] = 1-p;for(int i = 2; i <= t; ++i){f[i][0] = f[i-1][0] * (1-p);}for(int i = 2; i <= t; ++i){for(int j = 1; j <= n; ++j){if(j > i){break;}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 = 0; i <= n; ++i){if(i > t) break;ans += f[t][i] * i;} printf("%.8lf", ans);return 0;
}