Hướng dẫn bài POLE - Cột điện

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: