# Trồng cây (HSG9-2014, Hà Nội)

Không dễ nghĩ ra hướng làm ngay, cần thử trâu.

## $n \le 10$
- Mỗi cách trồng lại cây là một hoán vị $\rightarrow$ duyệt qua toàn bộ $n!$ hoán vị.
- Backtrack/ `next_permutation`

## $O(n^2)$

### Tiếp cận
Dễ thấy trường hợp đặc biệt, khi vị trí bị cố định nằm "đúng chỗ" thì đáp án là hiệu giữa $\max$ và $\min$.
"Đúng chỗ" tức là, nếu gọi $a'$ là mảng chứa các giá trị của $a$ được sắp xếp tăng, thì $a_k = a'_k$

### Giải
Ta sẽ điền lần lượt từng giá trị từ trái sang phải.
*Lưu ý: chữ $k$ sau đây khác chữ $k$ ở đề bài*
Nhận xét:
- Các giá trị không lên xuống theo các kiểu sau:  (Trong hình trên: $i < j < k$ là vị trí, $a < b < c$ là giá trị).
+ Không bao giờ ta điền vào ba vị trí $i,j,k$ lần lượt các số $a,c,b$ mà $a < b < c$, bởi cách này cho ra tổng chênh lệch là $c-a + c-b$. Trong khi nếu điền $a,b,c$ thì chênh lệch $=c-a$, nhỏ nhất. (tương tự cho trường hợp điền $c,a,b$)
+ Ngoại lệ: với vị trí bị cố định giá trị, buộc phải thuận theo nó mà có thể không điền được tối ưu nhất.

*$(*)$: vì có ràng buộc phải điền vào giá trị cố định với vị trí cho trước, nên bài toán mới khó.*
- Trường hợp điền lần lượt các giá trị $b,c,a$ (hoặc $b,a,c$) vào vị trí $i,j,k$: **Chưa** thể kết luận được ngay.
Ví dụ:
`1 4 0`, đi xuống $0$ trước tối ưu hơn (tổng $5$ và $7$)
nhưng với `1 4 -5`, đi xuống trước: $[1-(-5)] + [4-(-5)] = 15$, đi lên: $(4-1) + [4-(-5)] = 12$
$(1):$ Mặc dù nếu chỉ có ba số, dễ thấy bắt đầu từ giá trị $a$ ta có thể đi tới số gần nhất trong $b,c$ (tức $|b-a|$ nhỏ hơn thì chọn $b$, $|c-a|$ nhỏ hơn thì chọn $c$), là được tổng nhỏ nhất.
Tuy nhiên, khi xét tổng quát bài toán với $n$ số, do lựa chọn hiện tại ảnh hưởng tới tất cả lựa chọn phía sau đó. Ví dụ, từ ba số đầu tiên $a,b,c$, ta chèn thêm số $d$ vào phía sau, vậy thì $d$ phụ thuộc vào thứ tự của $b,c$. Nên không thể dùng thuật tham như $(1)$ được.
Vì lẽ đó **cần** xét hai khả năng: giá trị tiếp theo lớn/nhỏ hơn hẳn tất cả giá trị trước đó (lên/xuống hẳn).

- Luôn lấy các giá trị liên tiếp. Tức là, nếu các giá trị vừa được điền đang tăng dần, nếu số tiếp theo được điền vào theo trường hợp "tăng-tăng tiếp" (hình $2$), nó phải là giá trị **nhỏ nhất có thể**. Nếu không, sẽ xuất hiện xen kẽ như ý $1$.
Ví dụ: Đã điền được `1 0* 3`, còn lại hai số `5 4`. Đương nhiên phải điền `1 0* 3 4 5`.
Nếu tiếp theo, ta điền số nhỏ hơn, nó phải là giá trị **lớn nhất có thể**.
Ví dụ: đã điền `1 2 3*`, còn lại hai số `-1 0`, dĩ nhiên phải điền `1 2 3* 0 -1`.
Thật ra không cần biết là dãy đang tăng hay đang giảm, vì lúc nào điền ta cũng điền giá trị *gần sát* nhất có thể.

### Cài đặt
Đặt $f(l,r)$: giả sử đã điền xong số nhỏ nhất là (số thứ) $l$, lớn nhất là $r$. Chi phí tối ưu cho trạng thái này là bao nhiêu?
Cần thêm một chiều QHĐ
`[0/1]`: vị trí cuối cùng là số $l$ hay số $r?$ để ta có cơ sở tính chênh lệch.
Từ $f(l,r)$, xét số tiếp theo:
- nếu điền vào số $l-1$ thì đi tới trạng thái $f(l-1,r)$.
- tương tự cho $f(l,r+1)$

#### Vị trí $k$
Vị trí $k$ "phá đám" khi nó có khả năng (cao) là không gần sát với đoạn $[l,r]$ ta đã điền trước đó.
Một hướng giải quyết: "mặc kệ" $k$, mảng $a'$ lúc này chỉ quan tâm tới $n-1$ giá trị còn lại.
Với một trạng thái $f(l,r)$ bất kì, ta biết được đã điền $i = r-l+1$ số. Nếu $i+1 = k$ hoặc $i = k$, lúc này ta mới xét riêng để tổng chênh lệch được chính xác (nhưng vẫn cập nhật đi từ $f(l,r)$ tới $f(l,r)$ $(?!)$, do đó cần có một mảng phụ)

### Cảm nghĩ
Trên đây là một hướng suy nghĩ, không loại trừ khả năng có cách làm khác.