Hướng dẫn giải của Elaina và Đất nước của giải thuật
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người làm lời giải.
Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.
Tác giả:
Subtask 1:
Thử hết tất cả các trường hợp bằng cách duyệt quay lui
Độ phức tạp: $\mathcal O(2^{2\times n})$
Subtask 2:
Gọi ~dp_{i, j}~ là kết quả tối ưu nhất khi chọn ~a_i, b_j (|i-j| \le p)~ Ta có:
- ~dp_{i, j} = max(0, dp_{u, v}) + a_i + b_j~, với ~(u < i, v < j, |u-v| \le p)~
Độ phức tạp: $\mathcal O(n^{4})$
Subtask 3:
Tương tự như Subtask 2 chỉ khác lần này thay vì duyệt lại ~u, v~ mất 2 vòng for thì ta dùng mảng pref để tính ~max(0, dp_{u, v})~
Ta có:
- ~dp_{i, j} = pref_{i-1, j-1} + a_i + b_j~
- ~pref_{i, j} = max(\{pref_{i-1, j}, pref_{i, j-1}, dp_{i, j}\})~
Độ phức tạp : $\mathcal O(N^{2})$
Bình luận