題干：

Ilya got tired of sports programming, left university and got a job in the subway. He was given the task to determine the escalator load factor.

Let's assume that?n?people stand in the queue for the escalator. At each second one of the two following possibilities takes place: either the first person in the queue enters the escalator with probability?p, or the first person in the queue doesn't move with probability?(1?-?p), paralyzed by his fear of escalators and making the whole queue wait behind him.

Formally speaking, the?i-th person in the queue cannot enter the escalator until people with indices from?1?to?i?-?1?inclusive enter it. In one second only one person can enter the escalator. The escalator is infinite, so if a person enters it, he never leaves it, that is he will be standing on the escalator at any following second. Ilya needs to count the expected value of the number of people standing on the escalator after?t?seconds.

Your task is to help him solve this complicated task.

Input

The first line of the input contains three numbers?n,?p,?t?(1?≤?n,?t?≤?2000,?0?≤?p?≤?1). Numbers?n?and?t?are integers, number?p?is real, given with exactly two digits after the decimal point.

Output

Print a single real number — the expected number of people who will be standing on the escalator after?t?seconds. The absolute or relative error mustn't exceed?10?-?6.

Examples

Input

1 0.50 1

Output

0.5

Input

1 0.50 4

Output

0.9375

Input

4 0.20 2

Output

0.4

題目大意：

n個人在排成一隊在電梯面前，最前面的人每一秒鐘會進行一次選擇，有p的概率進電梯，有1-p的概率停在原地。每個人只有他前面的人都進電梯了，他才有可能進電梯。求t秒之后，進電梯人數的期望值。

解題報告：

? 看得出來，還是對概率dp的理解不是很透徹，換句話說是對dp的理解不是很透徹。轉移的時候別忘記乘以對應的概率。

? dp[i][j]代表i秒過后，電梯上有j個人的概率 。這樣就可以由兩個狀態轉移而來，但是注意這時候要注意這只是定義了某個狀態發生的概率，轉移的同時還要乘以轉移的概率，這兩個概率不是一個東西，所以不能直接疊加上來。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e3 + 5; int n,t; double p,dp[MAX][MAX];//i秒過后，電梯上有j個人的概率 int main() {cin>>n>>p>>t;dp[0][0]=1;for(int i = 1; i<=t; i++) {dp[i][0] = dp[i-1][0]*(1-p);for(int j = 1; j<=n; j++) {dp[i][j] = dp[i-1][j] * (j == n ? 1 : (1-p));dp[i][j] += dp[i-1][j-1] * p;}}double ans = 0;for(int i = 1; i<=n; i++) ans += dp[t][i]*i;printf("%.8f\n",ans);return 0 ; }

注意狀態的轉移不能直接疊加上來，比如說這樣：要么第i秒沒有人上來，那么就是i-1秒上來了j個人的概率；要么就是上來了一個人，就要乘以對應的概率。

for(int i = 1; i<=t; i++) {dp[i][0] = dp[i-1][0]*(1-p);for(int j = 1; j<=n; j++) {dp[i][j] = dp[i-1][j];dp[i][j] += dp[i-1][j-1] * p;}}

甚至還寫出了這種四不像：

//?? ?for(int i = 1; i<=n; i++) {
//?? ??? ?for(int j = 1; j<=t; j++) {
//?? ??? ??? ?dp[i][j] += dp[i][j-1];
//?? ??? ??? ?dp[i][j] += (1-dp[i][j-1])*p;?
//?? ??? ?}
//?? ?}

總結：

其實就BZOJ - 3036這個算 經過路徑長度的期望 一樣：

但是那代碼就要這么寫了：

using namespace std; int n, t; double p, dp[2005][2005];int main() {scanf("%d%lf%d", &n, &p, &t);dp[0][0] = 1;double ans = 0;for (int i = 0; i < t; ++i) {dp[i + 1][n] += dp[i][n];for (int j = 0; j < n; ++j) if (dp[i][j] > 1e-10) {dp[i + 1][j + 1] += dp[i][j] * p;dp[i + 1][j] += dp[i][j] * (1 - p);ans += dp[i][j] * p;}}printf("%.8f\n", ans);return 0; }

?

總結

以上是生活随笔為你收集整理的【CodeForces - 518D】Ilya and Escalator（概率dp，数学期望）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。