trang chủ / đề bài / chtline / lời giải

Mua thuyền (Convex Hull Trick)

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả: huunguyenhuunguyen

Hướng tiếp cận

Gọi fj là chi phí nhỏ nhất để đi từ vị trí 1 đến vị trí j. Theo đề bài:

f1=0,fj=min1≤i<j(fi+bi+ai·(j−i)).

Cài đặt trực tiếp cho O(N2) — quá chậm với N≤2·105.

Nhận xét quan trọng

Tách biểu thức trong min thành hàm tuyến tính theo j:

fi+bi+ai·(j−i)=ai·j+(fi+bi−ai·i).

Đặt đường thẳng Li(x)=ai·x+ci với ci=fi+bi−ai·i. Khi đó:

fj=mini<jLi(j).

Đây là bài toán cổ điển truy vấn giá trị nhỏ nhất của một họ đường thẳng tại một điểm cho trước. Vì các hệ số ai (slope) không nhất thiết đơn điệu, dùng Li Chao Tree.

Thuật toán

  1. Khởi tạo f1=0.
  2. Duy trì một Li Chao Tree trên miền x∈[1,N]. Mỗi nút lưu đường có giá trị nhỏ nhất tại điểm giữa của miền nút đó.
  3. Thêm đường L1 với slope a1, intercept c1=b1−a1.
  4. Với j=2,3,…,N:
    • fj= giá trị nhỏ nhất tại x=j trong Li Chao Tree.
    • Thêm đường Lj với slope aj, intercept cj=fj+bj−aj·j.
  5. In ra fN.

Li Chao Tree thực hiện cả add_line lẫn query trong O(logN).

Độ phức tạp

  • Thời gian: O(NlogN).
  • Bộ nhớ: O(N).

Với N=2·105, tổng số phép toán khoảng 3.6·106 — đủ nhanh cho cả C++ lẫn Python.


Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0