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.
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
Độ phức tạp theo lời giải phải là O(K*N) chứ ạ.
mình đã sửa, cám ơn bạn nhé