## Thuật toán quy hoạch động $\mathcal{O}(n^2\times k)$
Ý tưởng thuật quy hoạch động "trâu" của bài này khá dễ, đặt trạng thái quy hoạch động $\texttt{dp}[i][k]$ là chi phí tối thiểu để chia dãy $a[1\ldots i]$ thành $j$ đoạn. Công thức chuyển trạng thái là:
$$
\texttt{dp}[i][j] = \min_{1 \leq x \leq i}(\texttt{dp}[x - 1][j - 1] + (h[i] - h[x])^2)
$$
Cách làm trên có $n \times k$ trạng thái và chi phí chuyển là $\mathcal{O}(k)$ nên thuật toán có độ phức tạp $\mathcal{O}(n^2\times k)$
## Tối ưu bằng bao lồi
Biểu thức trong $\min$ có thể được biến đổi thành
$$\underbrace{-2\times h[x]\times h[i] + (h[x]^2+dp[x-1][j-1])} + h[i]^2$$
Phần biểu thức không nằm trên ngoặc chỉ phụ thuộc vào $i$ nên có thể coi là hằng số. Phần còn lại có dạng một phương trình đường thẳng với hệ số $a$ là $h[x]$ và hệ số $b$ là $h[x]^2+dp[x-1][j-1]$.
Vì thế ta có thể sử dụng convex hull trick hoặc Li-chao tree để tối ưu chi phí chuyển còn $\mathcal{O}(\log n)$ nếu sử dụng Line Container.
```cpp
for (int i = 1; i <= n; ++i) dp[i][1] = (h[i] - h[1]) * (h[i] - h[1]);
for (int j = 2; j <= k; ++j) {
LineContainer<true> cht; // Linecontainer truy vấn min
for (int i = 1; i <= n; ++i) {
if (dp[i - 1][j - 1] != INF) {
cht.add(h[i], h[i] * h[i] + dp[i - 1][j - 1]);
}
if (!cht.hull.empty())
dp[i][j] = cht.query(-2*h[i]) + h[i]*h[i];
}
}
cout << dp[n][k];
```
chithanhnguyen
Created at
0 likes