Hướng dẫn giải của [TS10 Phú Thọ 2025 - 2026] Chia kẹo
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 viết lời giải.
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.
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ưởng
Đặt ~T=Y-X~. Bài toán trở thành chọn nhiều hộp nhất có tổng đúng bằng ~T~. Dùng quy hoạch động một chiều, ~dp[s]~ là số hộp lớn nhất để đạt tổng ~s~. Với mỗi hộp có giá trị ~a_i~, duyệt ~s~ giảm dần và cập nhật ~dp[s]=\max(dp[s],dp[s-a_i]+1)~ nếu trạng thái trước tồn tại.
Độ phức tạp
~O(NT)~, với ~T \le 1000~.
Bình luận