Hướng dẫn giải của Bedao Mini Contest 22 - Chia kẹo
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ả: QioCass
Subtask 1:
Gọi ~f[i][j]~ là số cách xây dựng ~i~ cái kẹo, và số lượng kẹo trong túi cuối cùng là ~j~.
Công thức chuyển trạng thái: ~f[i][j]~ = ~\sum_{k = 1,|j - k| <= d}^{m} f[i - j][k]~, với ý nghĩa ~k~ là số lượng kẹo trong túi ngay trước túi đang xét hiện tại.
Trường hợp cơ sở: ~f[i][i] = 1, (1 \le i \le m)~.
Subtask 2:
Với ràng buộc ~m = 2~. Ta thấy công thức QHĐ lúc này là:
~f[i][1] = f[i - 1][1] + f[i - 1][2]~.
~f[i][2] = f[i - 2][1] + f[i - 2][2]~.
Hay có thể viết là ~dp[i] = dp[i - 1] + dp[i - 2]~, với ~dp[i] = f[i][0] + f[i][1]~.
Với thuật toán QHĐ thông thường mất độ phức tạp là ~O(n)~, nhưng với độ phức tạp như vậy sẽ không vượt qua được giới hạn của đề bài. Ta có thể giảm độ phức tạp xuống ~O(log(n))~ thông qua kĩ thuật Nhân ma trận hoặc Khử nhân ma trận.
Subtask 3:
Kết hợp cả Subtask 1 và Subtask 2. Ta sẽ dùng kĩ thuật Nhân ma trận để giải quyết bài toán này.
Để giảm số chiều của mảng ~f~, ta có thể gọi ~dp[i * m + j] = f[i][j]~.
Như vậy, độ phức tạp cho cả bài toán là ~O(K^3*log(n))~, với ~K = m * m = 100~.
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.