Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- - dp(i, T1, T2, T3, H1, H2, H3) là công thức quy hoạch động trâu nhất ta có thể nghĩ đến.
- - Để giảm thiểu bộ nhớ cho bài này ta sẽ lần lượt loại bớt đi những phần tử không cần thiết bằng một số đánh giá sau :
- +, T1 + T2 + T3 = sumT, từ đây ta sẽ vứt bớt đi một chiều T3
- +, gọi H3 = max(H1, H2, H3) = max(hi) với i chạy từ 1 -> n. Từ đây ta cũng có thể vứt đi chiều H3 ra ngoài
- - Còn lại T1, T2, H1, H2 : Ta sẽ nghĩ đến việc là biến dp từ bool trở thành int với ý nghĩa là như sau :
- +, dp(T1, T2) : là H1 + H2 nhỏ nhất mà ta có thể tạo được khi mà cấu hình 2 giá sách về chiều rộng là T1 và T2
- +, Nhận thấy là nếu ta sort giảm dần trong bài này thì cấu dp(T1, T2) chỉ được cập nhật khi mà T1 = 0 || T2 = 0. Nên việc ta tính H1 + H2 nhỏ nhất sẽ trở nên đơn giản
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement