Editorial for Atcoder Educational DP Contest K - Stones

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.

Độ phức tạp thời gian: ~O(N \times K)~.

Gọi ~dp[i]~ là khả năng Taro có thể thắng khi có ~i~ hòn đá. Ta sẽ chạy 2 vòng lặp, một vòng lặp cho các giá trị ~i (1 \leq i \leq K)~, vòng lặp còn lại cho mỗi giá trị trong ~A~. Nếu ~i \geq a_j ~, và chúng ta không thể thắng khi có ~i-a_j~ hòn đá, thì do đó ta có thể thắng được khi có ~i~ hòn đá. 

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    vector<bool> dp(k + 1);
    for (int i = 1; i <= k; ++i)
        for (int j : a)
            if (i >= j && !dp[i - j])
                dp[i] = 1;
    cout << (dp[k] ? "First" : "Second") << '\n';
}

Comments

Please read the guidelines before commenting.


  • 20
    ntnguyen  commented on Sept. 24, 2021, 3:51 a.m.

    Độ phức tạp theo lời giải phải là O(K*N) chứ ạ.


    • -1
      leduykhongngu  commented on Sept. 24, 2021, 4:05 a.m.

      mình đã sửa, cám ơn bạn nhé