Hướng dẫn giải của Đường Đi Chi Phí Nhỏ Nhất

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ả: huunguyen

Lời giải: Đường Đi Chi Phí Nhỏ Nhất

Hướng tiếp cận

Đặt $d p [x] [y]$ là chi phí nhỏ nhất để đến ô $(x, y)$ từ $(1, 1)$ .

Công thức truy hồi: $d p [x] [y] = min (d p [x] [y - 1] + x^{2}, d p [x - 1] [y] + c_{y})$

Vì $N$ lên đến $10^{9}$ , không thể lưu toàn bộ mảng $d p$ . Thay vào đó, ta xử lý từng cột $y$ từ trái sang phải và duy trì hàm $f_{y} (x) = d p [x] [y]$ dưới dạng hàm bậc hai từng đoạn (piecewise quadratic).

Nhận xét quan trọng

Tính lồi (convexity): Với mỗi cột $y$ cố định, $f_{y} (x)$ là hàm lồi theo $x$ . Cụ thể, $f_{y} (x + 1) - f_{y} (x) \leq f_{y} (x + 2) - f_{y} (x + 1)$ — hiệu sai phân không giảm.
Biểu diễn từng đoạn: Mỗi đoạn của $f_{y}$ có dạng: $f_{y} (x) = x^{2} \cdot (y - j) + x \cdot c_{j} + k$ trong đó $j$ là "cột nguồn" (cột mà ta di chuyển sang phải lần cuối), và $k$ là hằng số tích lũy.
Cập nhật sang cột mới: Chuyển từ $f_{y - 1}$ sang $f_{y}$ (thêm $c_{y}$ vào chi phí đi xuống): $f_{y} (x) = {min}_{i \leq x} (f_{y - 1} (i) + i^{2} + (x - i) \cdot c_{y}) = c_{y} \cdot x + {min}_{i \leq x} (f_{y - 1} (i) + i^{2} - i \cdot c_{y})$ Đây là "prefix minimum" của một hàm lồi — kết quả vẫn là hàm lồi.

Thuật toán

Duy trì stack các đoạn:

Mỗi phần tử stack lưu (lx, pre_col, k):

lx: hàng bắt đầu của đoạn này
pre_col: cột nguồn $j$ (cột di chuyển phải gần nhất)
k: hằng số; $f_{y} (x) = x^{2} (y - j) + x \cdot c_{j} + k$ với $x \geq l x$

Khi chuyển sang cột $y$ mới:

Lần lượt xóa các đoạn ở đuôi stack nếu chúng bị "thống trị" bởi đoạn mới (đoạn từ việc đi xuống ở cột $y$ hiện tại).
Tìm vị trí breakpoint chính xác bằng tìm kiếm nhị phân.
Thêm đoạn mới vào stack (tương ứng với việc di chuyển xuống từ breakpoint trở đi).

Trả lời truy vấn: Với truy vấn $(x, y)$ , tìm kiếm nhị phân trên stack của cột $y$ để xác định đoạn chứa hàng $x$ , rồi tính giá trị trực tiếp.

Khởi tạo cột 1: $d p [x] [1] = (x - 1) \cdot c_{1}$ , tức eval(pre_col=0, k=-c_0, x, col=0) = x \cdot c_0 - c_0.

Độ phức tạp

Thời gian: $O ((M + Q) \log N)$ — mỗi đoạn được thêm/xóa khỏi stack tối đa 1 lần, tìm kiếm nhị phân $O (\log N)$ ; mỗi truy vấn $O (\log M)$ .
Bộ nhớ: $O (M + Q)$

Bình luận

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