## Thuật toán $O(n^3)$
Gọi $\texttt{dp}[l][r]$ là điểm thưởng lớn nhất có thể thu được khi xét đoạn $[l, r]$. Vì khi chia dãy làm đôi, Cirno sẽ cố gắng cực tiểu hóa điểm thưởng nên ta có công thức chuyển trạng thái như sau:
$$
\texttt{dp}[l][r] = \max_{k\in[l, r - 1]}(\min(\texttt{dp}[l][k] + \texttt{sum}[l\ldots k], \texttt{dp}[k + 1][r] + \texttt{sum}[k + 1\ldots r]))
$$
trong đó $\texttt{sum}[l\ldots r] = a_l + a_{l + 1} + \ldots + a_r$. Kết quả chính là $\texttt{dp}[1][n]$.
Kết hợp với mảng cộng dồn, ta có $n^2$ trạng thái và chi phí chuyển là $O(n)$ nên ta thu được thuật toán có độ phức tạp $O(n^3)$
## Tối ưu quy hoạch động
Nhìn kỹ vào công thức chuyển trạng thái:
$$
\max_{k\in[l, r - 1]}(\min(\texttt{dp}[l][k] + \texttt{sum}[l\ldots k], \texttt{dp}[k + 1][r] + \texttt{sum}[k + 1\ldots r]))
$$
Bằng trực giác, ta có thể thấy rằng với $k \in [l, r-1]$: $\texttt{dp}[l][k] + \texttt{sum}[l\ldots k]$ là một đại lượng đồng biến, còn $\texttt{dp}[k + 1][r] + \texttt{sum}[k + 1\ldots r]$ là một đại lượng nghịch biến.
Vì, biểu thức trong ngoặc đạt $\max$ tại điểm mà hai hàm này "đụng nhau" (bạn đọc có thể vẽ ra để dễ hình dung).
$\rightarrow$ Ta có thể tối ưu chi phí chuyển xuống $O(\log n)$ bằng tìm kiếm nhị phân, hoặc $O(1)$ bằng hai con trỏ. Dưới đây là code minh họa sử dụng tìm kiếm nhị phân:
```cpp
const int INF = 1e18 + 5;
int n, a[MAXN], pref[MAXN], dp[MAXN][MAXN];
int calc_dp(int l, int r) {
if (l == r) return dp[l][r] = 0;
if (dp[l][r] != -INF) return dp[l][r]; // mảng dp ban đầu được gán là -INF
int left = l, right = r - 1;
int ans = -INF;
while (left <= right) {
int mid = (left + right) >> 1;
int cost_left = calc_dp(l, mid) + pref[mid] - pref[l - 1];
int cost_right = calc_dp(mid + 1, r) + pref[r] - pref[mid];
ans = max(ans, min(cost_left, cost_right));
if (cost_left < cost_right) left = mid + 1;
else right = mid - 1;
}
return dp[l][r] = ans;
}
```
## Cách làm khác
Một cách làm khác để tối ưu quy hoạch động xuống $O(n^2)$ là sử dụng [quy hoạch động chia để trị](https://wiki.vnoi.info/vi/algo/dp/dpdnc).
chithanhnguyen
Created at
2 likes