Hướng dẫn cho Máy Nghe Nhạc
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Subtask 1
- Sử dụng Backtracking để sinh mọi dãy chỉnh hợp, với mỗi dãy chỉnh hợp ta kiểm tra xem có thỏa mãn yêu cầu đề bài hay không.
Subtask 2
- Sử dụng Backtracking để sinh mọi xâu nhị phân độ dài \(n\), với mỗi xâu nhị phân ta kiểm tra xem có thỏa mãn yêu cầu đề bài hay không.
- Nếu xâu nhị phân có \(k\) phần tử được chọn thì sẽ có \(k!\) hoán vị thỏa mãn.
- Độ phức tạp thuật toán: \(O(2^n)\).
Subtask 3
- Sử dụng kĩ thuật Quy hoạch động để tính kết quả.
- DP Knapsack: Gọi \(dp[j][sum]\) là số cách chọn \(j\) phần tử, có tổng là \(sum\).
\(dp[0][0] = 0\), xét phần tử thứ \(i\) trong dãy \(a\), nếu \(dp[j-1][sum-a_i]\) khác 0 thì \(dp[j][sum] = dp[j][sum] + dp[j-1][sum-a_i]\).
Duyệt mọi \(dp[j][sum]\) thỏa mãn, kết quả là tổng của các \(dp[j][sum] \times j!\). - Độ phức tạp thuật toán: \(O(m \times n^2)\).
Bình luận
Mình nghĩ độ phức tạp subtask 3 là \(O(M.\)\(N^2\)\()\) chứ nhỉ ?