Trang chủ Bài tập Kỳ thi Bài nộp Xếp hạng Thảo luận Trợ giúp
Đăng nhập Đăng ký
Thảo luận
Thảo luận
POLE2 - Cột điện 2

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

Trùm CUỐI 2020-05-06 7:09:22 2020-05-07 2:51:29

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 F[i][x] là chi phí tối thiểu của i cột đầu tiên nếu cột i có chiều cao x .

Tính: F[i][x]=min⁡F[i-1][k]+c_{i-1}×|x-k|+(x-h_i )^2 với k≥h_i;|k-x|≤d .

Đáp số: min⁡F[n][x] . Độ phức tạp: O(n×h^2) .

Subtask 3:

Nhận thấy

  • F[i][x]=(F[i-1][k]+c_{i-1}\times k)-c_{i-1}\times x+(x-h_i )^2 với k∈[x,x+d]
  • F[i][x]=(F[i-1][k]-c_{i-1}\times k)+c_{i-1}\times x+(x-h_i )^2 với k∈[x-d,x]

Đặt:

  • Low[i-1][x]=min(F[i-1][k]-c_{i-1}\times k) với k∈[x-d,x]
  • High[i-1][x]=min⁡((F[i-1][k]+c_{i-1}\times k) với k∈[x,x+d]

Khi đó: F[i][x]=min⁡(Low[i-1][x]+c_{i-1}\times x,High[i-1][x]-c_{i-1}\times x)+(x-h_i )^2

Ta có thể tính: Low[i][x],High[i][x] sử dụng RMQ hoặc Interval Tree.

Độ phức tạp: O(n×hmax×log_⁡h)

Tổng cộng 1 trả lời

vu thi thanh hoa
2022-11-16 1:36:33
Chuyên Sơn La Online Judge.
Mã nguồn mở cho giải pháp chấm bài trực tuyến (Online Judge): DMOJ - UOJ - QDUOJ - SYZOJ - OJS - SHARIF - AURORA - CMS