gọi **dp[i][k]** là số tiền tối thiểu tính tới vị trí thứ **i** và nâng cột **i** lên **k**.
$$
dp[i][k] = \min \left( dp[i - 1][x] + c(i - 1) \cdot \left| a[i] + k - a[i - 1] + x \right| + k^2 \right)
$$
tức nhiên là khoảng cách của 2 thằng không quá **d**.
ta có ở đây **k²** và **c[i - 1]** là cố định, phải tìm cái **abs(...) là nhỏ nhất thì nó mới nhỏ nhất**.
với một thằng **a[i] + k**, vì khoảng cách không quá **d** cho nên là các số thỏa mãn chỉ có thể từ:
$$
a[i] + k - d \quad \text{tới} \quad a[i] + k + d
$$
vậy đối với **a[i - 1]** thì các số có thể giao động:
$$
a[i] + k - d \le a[i - 1] + x \le a[i] + k + d
$$
\=>
$$
a[i] - a[i - 1] + k - d \le x \le a[i] - a[i - 1] + k + d
$$
bài toán của mình là lấy:
$$
\min \left( dp[i - 1][a[i] - a[i - 1] + k - d] \; \text{tới} \; dp[i - 1][a[i] - a[i - 1] + k + d] \right)
$$
thì **Seg** cũng ok đấy nhưng mà ở đây là **hàng đợi đơn điệu**.
vậy mình có thể **min trên đoạn tịnh tiến** không? **Có đó**.
với mỗi thằng **k bắt đầu từ 0** thì mình có thể **min trên đoạn** được rất ổn.
TENJOKE
Created at
0 likes