## Thuật toán "ngây thơ"
Bài toán có mô hình chia đoạn khá quen thuộc, ta có ý tưởng đặt trạng thái quy hoạch động như sau: Gọi $\texttt{dp}[i][j]$ là chi phí tối thiểu để chia dãy $a[1\ldots i]$ thành $j$ phần. Công thức chuyển trạng thái là:
$$
\texttt{dp}[i][j] = \min_{l < i}(\texttt{dp}[l][k - 1] + \max(a[l + 1\ldots i]))
$$
Số trạng thái là $n\times k$, nếu ta duyệt lại đoạn $[l + 1\ldots i]$ để tính $\max$ thì chi phí chuyển là $O(n^2)$ từ độ phức tạp thuật toán là $O(n^3\times k)$. Ta có thể tối ưu xuống $O(n^2\times k)$ bằng cách cập nhật $\max$ ngay trong quá trình duyệt.
## Tối ưu chi phí chuyển
Ý tưởng chính là tối ưu hóa chi phí chuyển trạng thái. Gọi $\texttt{left}[i]$ là vị trí gần nhất về phía bên trái của $i$ sao cho $a_{\texttt{left}[i]} > a_i$. Khi đó ta có thể chuyển trạng thái:
$$\texttt{dp}[i][j] = \min(\texttt{dp}[\texttt{left}[i]][j], \min_{l\in [\texttt{left}[i],j-1]}\texttt{dp}[l][j - 1] + a[i])$$
Sở dĩ ta có công thức chuyển kia vì ta luôn có $\max(a[l+1\ldots j]) = a[i]$.
Sử dụng một cấu trúc dữ liệu truy vấn phạm vi (ví dụ là segment tree) chi phí chuyển giảm xuống $O(\log n)$ (vẫn chưa đủ nhanh với $n \leq 2\times 10^5$). Vì thế ta có thể tính $\min$ song song với tính mảng $\texttt{left}$ bằng cách lưu một `pair` dạng ($\texttt{dp}$, vị trí) trong `stack`:
```cpp
vector<pii> st;
for (int j = 2; j <= k; ++j) {
for (int i = j; i <= n; ++i) {
int cand = dp[i - 1][j - 1];
while (!st.empty() && a[st.back().se] <= a[i]) {
cand = min(cand, st.back().fi);
st.pop_back();
}
dp[i][j] = min(dp[st.empty() ? 0 : st.back().se][j], cand + a[i]);
st.push_back({cand, i});
st.clear();
}
```
Lúc này độ phức tạp của thuật toán là $O(n\times k)$ (vẫn cần cài đặt khéo để không bị TLE T-T)
## Tối ưu bộ nhớ
Để ý trong công thức $\texttt{dp}[i][j]$ chỉ phụ thuộc vào $\texttt{dp}[x][j - 1]$ nên một hướng tối ưu là chỉ lưu hai hàng $\texttt{dp}$ liên tiếp nhau. Việc này giúp giảm bộ nhớ cache nên cũng giảm thời gian chạy.
## Thuật toán "ngây thơ"
Bài toán có mô hình chia đoạn khá quen thuộc, ta có ý tưởng đặt trạng thái quy hoạch động như sau: Gọi $\texttt{dp}[i][j]$ là chi phí tối thiểu để chia dãy $a[1\ldots i]$ thành $j$ phần. Công thức chuyển trạng thái là:
$$
\texttt{dp}[i][j] = \min_{l < i}(\texttt{dp}[l][k - 1] + \max(a[l + 1\ldots i]))
$$
Số trạng thái là $n\times k$, nếu ta duyệt lại đoạn $[l + 1\ldots i]$ để tính $\max$ thì chi phí chuyển là $O(n^2)$ từ độ phức tạp thuật toán là $O(n^3\times k)$. Ta có thể tối ưu xuống $O(n^2\times k)$ bằng cách cập nhật $\max$ ngay trong quá trình duyệt.
## Tối ưu chi phí chuyển
Ý tưởng chính là tối ưu hóa chi phí chuyển trạng thái. Gọi $\texttt{left}[i]$ là vị trí gần nhất về phía bên trái của $i$ sao cho $a_{\texttt{left}[i]} > a_i$. Khi đó ta có thể chuyển trạng thái:
$$\texttt{dp}[i][j] = \min(\texttt{dp}[\texttt{left}[i]][j], \min_{l\in [\texttt{left}[i],j-1]}\texttt{dp}[l][j - 1] + a[i])$$
Sở dĩ ta có công thức chuyển kia vì ta luôn có $\max(a[l+1\ldots j]) = a[i]$.
Sử dụng một cấu trúc dữ liệu truy vấn phạm vi (ví dụ là segment tree) chi phí chuyển giảm xuống $O(\log n)$ (vẫn chưa đủ nhanh với $n \leq 2\times 10^5$). Vì thế ta có thể tính $\min$ song song với tính mảng $\texttt{left}$ bằng cách lưu một `pair` trong `stack`:
```cpp
vector<pii> st;
for (int j = 2; j <= k; ++j) {
for (int i = j; i <= n; ++i) {
int cand = dp[i - 1][j - 1];
while (!st.empty() && a[st.back().se] <= a[i]) {
cand = min(cand, st.back().fi);
st.pop_back();
}
dp[i][j] = min(dp[st.empty() ? 0 : st.back().se][j], cand + a[i]);
st.push_back({cand, i});
st.clear();
}
```
Lúc này độ phức tạp của thuật toán là $O(n\times k)$ (vẫn cần cài đặt khéo để không bị TLE T-T)
## Tối ưu bộ nhớ
Để ý trong công thức $\texttt{dp}[i][j]$ chỉ phụ thuộc vào $\texttt{dp}[.][j - 1]$ nên một hướng tối ưu là chỉ lưu hai hàng $\texttt{dp}$ liên tiếp nhau. Việc này giúp giảm bộ nhớ cache nên cũng giảm thời gian chạy.
chithanhnguyen
Created at
3 likes