Codeforces 768D(概率DP)

Codeforces 768D
设$dp(i,j)$为前$i$天生产了$j$种不同的水晶的概率,转移方程:
$$dp(i,j)=dp(i-1,j) \times \frac{j}{k} + dp(i-1,j-1) \times \frac{k-j+1}{k}$$
之后判断$dp(i,k)$是否大于给定条件,答案为$i$
然后因为$p<=1000$,所以把所有情况先预处理出来,直接输出即可。
此题可以把第一维压掉,注意$eps=1e-7$不要写作$eps=1e7$

Codeforces Submission

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXQ = 1000 + 5;
const db eps = 1e-7;
int now, k, Q, ans[MAXQ];
db dp[MAXQ];
void clean() {
ms(dp, 0), dp[0] = 1.0, now = 1;
}
void solve() {
clean();
for (int i=1;now<=1000;i++) {
for (int j=k;j>0;j--) dp[j] = (dp[j] * (db)j + dp[j-1] * (db)(k-j+1)) / (db)k;
while (now <= 1000 && dp[k] * 2000.0 >= (now - eps)) {
ans[now] = i, now++;
}
dp[0] = 0.0;
}
for (int i=1;i<=Q;i++) {
int p;
scanf("%d", &p);
printf("%d\n", ans[p]);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
scanf("%d%d", &k, &Q), solve();
return 0;
}

------ 本文结束 ------