2015年3月2日 星期一

[CF 518D] Ilya and Escalator

作法:

一般的機率DP題,去作過了 i 秒且現在有 j 個人在上面的機率就好了。

code :

#include<bits/stdc++.h>
#define DB double
using namespace std;
const int maxn=2000+10 ;
 
DB dp[maxn][maxn] ;
 
main()
{
    int n,t ; DB p ;
    scanf("%d%lf%d",&n,&p,&t) ;
    dp[0][0]=1.0 ;
    for(int i=1;i<=t;i++) for(int j=0;j<=n;j++)
    {
        if(j==n) dp[i][j]=p*dp[i-1][j-1]+dp[i-1][j] ;
        else dp[i][j]= j ? p*dp[i-1][j-1]+(1-p)*dp[i-1][j] :
            (1-p)*dp[i-1][j] ;
    }
    DB ans=0.0 ;
    for(int i=1;i<=n;i++) ans+=dp[t][i]*i ;
    printf("%.9f\n",ans) ;
}
 

沒有留言:

張貼留言