# QHĐ chia để trị - DP DnC
[Contest](https://lqdoj.edu.vn/contest/22a5qhdchiadetri)

## SEQ
Thật ra không phải là chia để trị mà chỉ là tối ưu QHĐ thôi.
$f(l,r) = 1 + \max(f(l,m), f(m+1,r))$ nếu tổng $l..m$ $=$ tổng $m+1..r$.
Chứng minh ĐPT?

### Chia để trị là gì?
Có các đặc điểm:
- Phân rã bài toán lớn thành nhiều bài toán con
- Bài toán con phải có **cùng bản chất** với bài toán lớn, và thông thường ta sẽ chia thành những phần bằng nhau
- Gọi đệ quy để tính bài con
- Tổng hợp lại để ra bài lớn.

Chi tiết mời xem Tài liệu giáo khoa chuyên Tin + DSAP Textbook: [(VNOI)](https://vnoi.info/wiki/algo/basic/Tai-Lieu-Thuat-Toan.md)

Vậy:

void dnc(int l, int r) {
    if (l > r) return;
    if (l == r) {
        giải_trường_hợp_gốc;
        return ;
    }
    int m = (l+r) / 2;
    dnc(l,m);
    dnc(m+1,r);
}

sẽ là hình mẫu chung của chia để trị.
Ngược lại, nếu điểm chia $m$ không phải vị trí chính giữa thì ĐPT sẽ rơi vào $O(n^2)$ trong worst-case [Xem ảnh].

### Độ phức tạp
Do chia đôi theo tổng nên số tầng tối đa là $O(\log(\sum a))$

## Pagoda
Mảng QHĐ & công thức:
- Đặt $f(i,j)$ là nếu để $i$ ông thầu xây cầu thang ở các vị trí từ $1$ tới $j$, thì chi phí $\min$ là bao nhiêu?
- Có $f(i,j) = \min\{ f(i-1,k) + cost(k+1,j) \enspace \forall \enspace 1 \le k < j \}$ (giả sử ông thứ $i$ xây đoạn $[k+1,j]$)

Vậy cách làm thông thường sẽ là 3 vòng for.
Nhận thấy công thức trên thuộc vào dạng 3, theo [đây](https://codeforces.com/blog/entry/8219) nên áp dụng được DP DnC $(*)$.
$(*)$ *Ngoài ra còn phải thỏa điều kiện điểm chia tối ưu tăng dần hoặc BĐT tứ giác. Tuy nhiên thường thì những điều này chứng minh toán khá phức tạp nên cứ dùng trực giác*.

### Điểm khó
Để thuật hiệu quả, phải tính được $cos$t trong $O(1)$.

#### $k = 1$
Chọn một số để tổng chênh lệch tới nó là bé nhất.
Đây là bài toán quen thuộc, chọn trung vị.

#### $k = 2$
Nhân tung tóe để có được các hạng tử liên quan.
Có $|a_i - v|^2 = a_i^2 - 2.a_i.v + v^2$.
Ta thấy $a$ là các số cho trước, cố định. Nếu nhóm các số hạng theo bậc của $v$ thì sẽ có một biểu thức bậc 2:
$A \times v^2 + B \times v + C$.
Áp dụng kiến thức toán, ta thấy điểm rơi của hàm bậc hai nằm ngay tại gốc parabola.

#### Tổng kết
Cần dùng prefix-sum.

### Phần chia để trị
Làm theo sườn chung như ở [cp-algo](https://cp-algorithms.com/dynamic_programming/divide-and-conquer-dp.html#generic-implementation).
Mẹo ghi nhớ: Vì $dp(i)$ hoàn toàn phụ thuộc vào $dp(i-1)$ nên ta đi tính từng dòng của $dp$.
Điều kiện áp dụng CĐT là: $P[i][j] \le P[i][j+1]$ (điểm chia tối ưu tăng dần). Từ đó có ý tưởng truyền thêm tham số $opt_L, opt_R$ để việc tìm điểm $opt$ cho các vị trí được gọi đệ quy xuống nhanh hơn (Vì chỉ chạy một đoạn ngắn hơn $[opt_L, opt_R]$ thay vì từ $l \rightarrow r$).
Thực tế, nhờ có `opt_l, opt_r` mà tổng độ dài ta phải xét ở mỗi tầng bằng đúng $O(n)$.
Thêm nữa, nhờ có chia để trị mà số tầng là $O(\log n)$

## SEQPART
wow