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.

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

Hãy đọc nội quy trước khi bình luận.



  • 1
    khanhss  đã bình luận lúc 1, Tháng 5, 2023, 11:16 chỉnh sửa

    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


  • 4
    tnhu_0508  đã bình luận lúc 1, Tháng 8, 2022, 6:08

    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 ạ


    • 2
      damtrungduc  đã bình luận lúc 7, Tháng 10, 2022, 8:56

      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


      • 0
        quyet  đã bình luận lúc 5, Tháng 8, 2023, 13:30

        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


  • 4
    Rukashi  đã bình luận lúc 15, Tháng 2, 2022, 8:49

    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 :(