Subtask 1:
Sử dụng duyệt chọn các giá trị từng cột. Độ phức tạp O(3^n)
Subtask 2:
Gọi là chi phí tối thiểu của cột đầu tiên nếu cột có chiều cao .
Tính: với .
Đáp số: .
Độ phức tạp: .
Subtask 3.:
Nhận thấy
- với
- với
Đặt:
với
với
Ta có thể tính: . Tương tự với . Việc tính toán mảng thực hiện trong
Khi đó:
Độ phức tạp:
Tổng cộng 1 trả lời