Editorial for Atcoder Educational DP Contest I - Coins


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: 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;
}

Comments

Please read the guidelines before commenting.



  • 3
    tnhu_0508   commented on Aug. 1, 2022, 1:08 p.m.

    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 ạ


    • 0
      damtrungduc   commented on Oct. 7, 2022, 3:56 p.m.

      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


  • 4
    Rukashi   commented on Feb. 15, 2022, 3:49 p.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 :(