Codeforces 768D：Jon and Orbs

Codeforces 768D：Jon and Orbs

题目链接：http://codeforces.com/contest/768/problem/D

题目大意：共有k种蛋，每天随机孵化其中一个，每次query每种蛋都至少有一个的概率>p_i/2000需要多少天，一共询问q次。

概率dp

定义状态：dp[第i天][已孵化j种蛋]为改装状态下的概率;

状态转移方程：dp[i][j]=[1-(j-1)/k]*dp[i-1][j-1]+(j/k)*dp[i-1][j];

/*需要注意的是dp[i][0]=0，其中i>1*/

我们可以离线处理所有询问（按p_i升序排列），再恢复原排列输出，已达到询问总复杂度O（nlgn），

观察到1≤p_i≤1000，故亦可以保存对应p_i=1 to 1000的ans，达到询问总复杂度O（n）.

代码如下：

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 #define N 1005
 5 using namespace std;
 6 int n,k,q,ans[N],p;
 7 double dp[10*N][N];
 8 int main(void){
 9     scanf("%d%d",&n,&q);
10     dp[0][0]=1;
11     for(int i=1;i<10*N;++i){
12         dp[i][0]=0;
13         for(int j=1;j<=n;++j)
14             dp[i][j]=(dp[i-1][j-1]*(n-j+1)+dp[i-1][j]*j)/n;
15     }
16     for(int i=1;i<=1000;++i){
17         while(dp[k][n]*2000<i)k++;
18         ans[i]=k;
19     }
20     while(q--){
21         scanf("%d",&p);
22         printf("%d
",ans[p]);
23     }
24 }