Nhà kính của Sprout

Hướng tiếp cận

Bài toán tương đương với bài toán Post Office kinh điển: đặt $K$ cơ sở trên đường thẳng để tối thiểu tổng khoảng cách tuyệt đối từ $N$ điểm đến cơ sở gần nhất.

Ta giải bằng quy hoạch động kết hợp tối ưu chia để trị (Divide and Conquer Optimization).

Nhận xét quan trọng

1. Sắp xếp: Sau khi sắp xếp các vị trí cây, phân hoạch tối ưu luôn chia thành $K$ đoạn con liên tiếp - mỗi đoạn được phục vụ bởi một nhà kính.

2. Vị trí tối ưu cho một đoạn: Với đoạn cây $[l,r]$, nhà kính tối ưu nằm tại trung vị $x_m$ (với $m=\lfloor (l+r)/2\rfloor$), cho chi phí ${\sum }_{i=l}^r|x_i-x_m|$.

3. Tính nhanh chi phí đoạn: Dùng mảng tổng tiền tố (prefix sum), ta tính chi phí đoạn $[l,r]$ trong $O(1)$: $$\text{cost}(l,r)=(m-l)·x_m-(S_m-S_l)+(S_{r+1}-S_{m+1})-(r-m)·x_m$$ trong đó $S_i=x_0+x_1+\dots +x_{i-1}$.

4. Bất đẳng thức tứ giác: Hàm $\text{cost}(l,r)$ thỏa mãn bất đẳng thức tứ giác (quadrangle inequality), tức là: $$\text{cost}(a,c)+\text{cost}(b,d)\le \text{cost}(a,d)+\text{cost}(b,c)\forall a\le b\le c\le d$$ Điều này cho phép áp dụng tối ưu chia để trị trên DP.

Thuật toán

1. Sắp xếp các vị trí $x_1,\dots ,x_N$.

2. Xây dựng mảng tổng tiền tố $S$.

3. DP cơ sở ($k=1$): $\text{dp}[i]=\text{cost}(0,i-1)$ cho mọi $i$.

4. DP lặp cho $k=2,3,\dots ,K$: $${\text{dp}}_k[i]={min}_{j<i}({\text{dp}}_{k-1}[j]+\text{cost}(j,i-1))$$

   Gọi $\text{opt}(i)$ là giá trị $j$ tối ưu cho ${\text{dp}}_k[i]$. Nhờ bất đẳng thức tứ giác, ta có $\text{opt}(i)\le \text{opt}(i+1)$. Điều này cho phép dùng chia để trị:

   • Với đoạn $[lo,hi]$, tính ${\text{dp}}_k[\text{mid}]$ bằng cách duyệt $j\in [\text{opt\_lo},\text{opt\_hi}]$.
   • Tìm $\text{opt}(\text{mid})$, sau đó đệ quy:
     • Nửa trái $[lo,\text{mid}-1]$ với $\text{opt}\in [\text{opt\_lo},\text{opt}(\text{mid})]$
     • Nửa phải $[\text{mid}+1,hi]$ với $\text{opt}\in [\text{opt}(\text{mid}),\text{opt\_hi}]$

5. Kết quả: ${\text{dp}}_K[N]$.

Độ phức tạp

• Thời gian: $O(N\log N+N·K·\log N)$. Sắp xếp $O(N\log N)$, mỗi vòng DP tốn $O(N\log N)$ nhờ chia để trị, lặp $K$ vòng.
• Bộ nhớ: $O(N)$ - chỉ cần lưu hai hàng DP.