Hướng dẫn giải của Atcoder Educational DP Contest I - Coins
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả: ncduy0303
Gọi ~dp[i][j]~ là xác suất để có ~j~ mặt ngửa sau khi tung ~i~ đồng xu đầu tiên. Xác suất này có thể được tính bằng cách lấy tổng xác suất của hai trường hợp:
- Đồng xu thứ ~i~ là mặt ngửa, và ~i-1~ đồng xu trước đó có ~j-1~ mặt ngửa. Xác suất của trường hợp này là ~dp[i-1][j-1] \cdot p[i]~
- Đồng xu thứ ~i~ là mặt sấp, và ~i-1~ đồng xu trước đó có ~j~ mặt ngửa. Xác suất của trường hợp này là ~dp[i-1][j] \cdot (1-p[i])~
Do đó, công thức quy hoạch động là:
~dp[i][j]=dp[i−1][j−1] \cdot p[i]+dp[i−1][j] \cdot (1−p[i])~
Độ phức tạp: ~O(N^{2})~
Code tham khảo
#include<bits/stdc++.h> using namespace std; long double dp[3001][3001]; int main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; vector<long double> p(n + 1); for(int i = 1; i <= n; ++i) cin >> p[i]; int leastHeads = n / 2 + 1; for (int i = 0; i <= n; ++i) dp[i][0] = 1; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= leastHeads; ++j) { dp[i][j] = dp[i - 1][j - 1] * p[i] + dp[i - 1][j] * (1 - p[i]); } } cout << fixed << setprecision(10) << dp[n][leastHeads] << endl; }
Bình luận
Một cách làm khác dễ hiểu hơn của mình với việc tính tổng xác suất những lần số mặt của > n/2:
code của b đúng ý mình luon, dễ hiểu, cách của ad ngẫm mãi ko ra
biến cố đối ấy bn. Nếu giả sử xác xuất xảy ra pi nào đó là 40% tức là 0,4 thì ko xảy ra pi là 60% tức là 100 % - 40% tức là 1 - 0,4
mọi người cho mình cái dòng leastHeads với ạ , tại sao mình lại chỉ duyệt tới đó thoi vậy ạ
vì xu ngửa lớn hơn xu sấp nên chỉ cần lượng xu ngửa lớn hơn quá bán là đc
sao ko chạy đến n nhỉ :< vì từ n/2+1 đến n nó cx lớn hơn 1 nửa mà nhỉ mình ch hiểu lắm
Cho mình hỏi là vì sao xác suất tất cả các mặt đều sấp từ 1-n là 1 vậy :(