[Quy hoạch động] [Tham lam] [UVa] 757

Đề bài
Hướng làm
Bước 1: Quy hoạch động thời gian đi từ hồ 1 đến hồ i
Bước 2:
Giả sử ta chỉ câu cá ở các hồ từ hồ 1 đến hồ i
Ta dễ dàng tính được thời gian câu thực tế sau khi trừ đi thời gian di chuyển.
Với mỗi 5 phút, ta xem trong 5 phút ấy câu ở hồ nào lợi nhất thì phân bổ thời gian 5 phút vào hồ đó. Để giảm độ phức tạp, ta có thể dùng heap.
Code

[Quy hoạch động] [Bitmask] [Floyd] [UVa] 1281

Đề bài
Hướng làm:
Bước 1: Dùng thuật toán Floyd tìm đường đi ngắn nhất giữa mọi cặp đỉnh
Bước 2: Chia đường đi thành 4 phần rồi quy hoạch động giống dạng TSP (Traveling Saleman)
Code

[Quy hoạch động] [UVa] 11259

Đề bài
Gọi dp[i] là số cách đổi i đồng, với số lượng mỗi đồng không giới hạn.
Để có được kết qủa, ta dùng phương pháp bao hàm và loại trừ, tức là trừ các cách đổi i đồng thành nhiều hơn d[1] đồng 1, nhiều hơn d[2] đồng 2, ... rồi cộng tiếp số cách đổi i đồng thành nhiều hơn d[1] đồng 1 và d[2] đồng 2,... (xem kĩ hơn trong code).
Code

[Quy hoạch động] [UVa] 1105

Đề bài
Hướng làm
Vì khoảng cách trong đề bài là khoảng cách Manhattan nên ta xoay hệ tọa độ 45 độ để biến đổi bài toán thành bài toán tìm hình chữ nhật có tổng lớn nhất trong bảng.
Code
Test