Đường Đi Chi Phí Nhỏ Nhất

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

Hướng tiếp cận

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

Công thức truy hồi: $$dp[x][y]=min(dp[x][y-1]+x^2,dp[x-1][y]+c_y)$$

Vì $N$ lên đến ${10}^9$, không thể lưu toàn bộ mảng $dp$. 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)=dp[x][y]$ dưới dạng hàm bậc hai từng đoạn (piecewise quadratic).

Nhận xét quan trọng

1. 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)\le f_y(x+2)-f_y(x+1)$ — hiệu sai phân không giảm.

2. Biểu diễn từng đoạn: Mỗi đoạn của $f_y$ có dạng: $$f_y(x)=x^2·(y-j)+x·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.

3. 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\le x}(f_{y-1}(i)+i^2+(x-i)·c_y)=c_y·x+{min}_{i\le x}(f_{y-1}(i)+i^2-i·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·c_j+k$ với $x\ge lx$

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

1. 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).
2. Tìm vị trí breakpoint chính xác bằng tìm kiếm nhị phân.
3. 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: $dp[x][1]=(x-1)·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)$