Advertisement
trungore10

SOL_bookcase

Dec 6th, 2018
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.95 KB | None | 0 0
  1. - 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.
  2.  
  3. - Để 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 :
  4. +, T1 + T2 + T3 = sumT, từ đây ta sẽ vứt bớt đi một chiều T3
  5. +, 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
  6.  
  7. - 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 :
  8. +, 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
  9. +, 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