Gợi ý bài WATERMOV - Chuyển nước

Link bài WATERMOV - Chuyển nước

• Gọi là dãy tổng trước của dãy , tức là .
• Với mỗi , ta coi là một điểm trong mặt phẳng tọa độ . Khi đó ta có nhận xét: Dãy là dãy không giảm khi và chỉ khi dãy điểm thỏa mãn khi đi từ không rẽ phải (tức là đi thắng hoặc rẽ trái).
• Thuật toán (không biết lý thuyết này ở đâu):
  • Tìm dãy bao lồi dưới của dãy , giả sử được dãy
  • Diện tích đa giác tạo bởi dãy trên chính là chi phí chuyển nước.