Tác giả: Nguyễn Hữu Nhật Quang

Dễ thấy, để vận chuyển toàn bộ gỗ từ ô ~(i, j)~ sang ô ~(u, v)~ thì tổng chi phí sẽ là ~a_{ij} \times (|i - u| + |j - v|)~. Ta có thể tách thành ~a_{ij} \times |i - u| + a_{ij} \times |j - v|~.

Đặt ~R_{ij} = a_{ij} \times |i - u|, C_{ij} = a_{ij} \times |j - v|~. Hiển nhiên ta có:

~R_{i1} + R_{i2} + ... + R_{im} = (a_{i1} + a_{i2} + ... + a_{im}) \times |i - u|~ ~(*)~

Tương tự với ~C~.

Gọi ~SR_i~ là tổng các số trên hàng ~i~ và ~SC_i~ là tổng các số trên cột ~i~. Ta có thể viết lại ~(*)~ thành:

~\sum^{j \le m}_{j = 1} R_{ij} = R_{i1} + R_{i2} + ... + R_{im} = SR_i \times |i - u|~

Tương tự:

~\sum^{i \le m}_{i = 1} C_{ij} = C_{1j} + C_{2j} + ... + C_{nj} = SC_j \times |j - v|~

Vậy tổng chi phí vận chuyển toàn bộ gỗ từ tất cả các ô đến một ô ~(u, v)~ có thể được viết lại thành:

~\sum^{i \le n}_{i = 1} \sum^{j \le m}_{j = 1} R_{ij} + C_{ij} = \sum^{i \le n}_{i = 1} (\sum^{j \le m}_{j = 1} R_{ij}) + \sum^{j \le m}_{j = 1} (\sum^{i \le n}_{i = 1} C_{ij})~

~= \sum^{i \le n}_{i = 1} SR_i \times |i - u| + \sum^{j \le m}_{j = 1} SC_i \times |j - v|~ ~(**)~

Chúng ta có thể dễ dàng tính được hai mảng ~SR~ và ~SC~. Nhận thấy rằng hai số hạng trong ~(**)~ không liên quan gì đến nhau, ta có thể tách chúng ra để tính riêng.

Đặt ~A_u = \sum^{i \le n}_{i = 1} SR_i \times |i - u|~. Bây giờ ta cần tính ~A_{u + 1}~ từ ~A_u~. Nhận thấy rằng, với ~i \le u~, khi chuyển từ ~A_u~ sang ~A_{u + 1}~ thì tổng chi phí tăng lên ~SR_i~ (có thể hình dung như việc thay vì bạn chuyển các khối gỗ đến hàng ~i~ thì bạn phải chuyển chúng đến hàng ~i + 1~). Ngược lại, với ~i > u~ thì tổng chi phí sẽ giảm đi ~SR_i~.

Từ đây, ta viết được công thức tính ~A_{u + 1}~ từ ~A_u~ như sau:

~A_{u + 1} = A_u + (SR_1 + SR_2 + ... + SR_u) - (SR_{u + 1} - SR_{u + 2} + ... + SR_n)~

Đến đây, ta có thể dễ dàng tính được mọi ~A_i~ sử dụng mảng tổng tiền tố. Tương tự với mảng ~SC~ và chi phí vận chuyển cho các cột.

Độ phức tạp: ~O(mn)~.