Hướng dẫn giải của Nhà kính của Sprout

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

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

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.
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 = ⌊ (l + r) / 2 ⌋$ ), cho chi phí $\sum_{i = l}^{r} | x_{i} - x_{m} |$ .
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)$ :
$cost (l, r) = (m - l) \cdot x_{m} - (S_{m} - S_{l}) + (S_{r + 1} - S_{m + 1}) - (r - m) \cdot x_{m}$
trong đó $S_{i} = x_{0} + x_{1} + \dots + x_{i - 1}$ .
Bất đẳng thức tứ giác: Hàm $cost (l, r)$ thỏa mãn bất đẳng thức tứ giác (quadrangle inequality), tức là:
$cost (a, c) + cost (b, d) \leq cost (a, d) + cost (b, c) \forall a \leq b \leq c \leq d$
Điều này cho phép áp dụng tối ưu chia để trị trên DP.

Thuật toán

Sắp xếp các vị trí $x_{1}, \dots, x_{N}$ .
Xây dựng mảng tổng tiền tố $S$ .
DP cơ sở ( $k = 1$ ): $dp [i] = cost (0, i - 1)$ cho mọi $i$ .
DP lặp cho $k = 2, 3, \dots, K$ :
dpk[i]=minj<i(dpk−1[j]+cost(j,i−1))
Gọi $opt (i)$ là giá trị $j$ tối ưu cho ${dp}_{k} [i]$ . Nhờ bất đẳng thức tứ giác, ta có $opt (i) \leq opt (i + 1)$ . Điều này cho phép dùng chia để trị:
- Với đoạn $[l o, h i]$ , tính ${dp}_{k} [mid]$ bằng cách duyệt $j \in [opt_lo, opt_hi]$ .
- Tìm opt(mid), sau đó đệ quy:
  - Nửa trái $[l o, mid - 1]$ với $opt \in [opt_lo, opt (mid)]$
  - Nửa phải $[mid + 1, h i]$ với $opt \in [opt (mid), opt_hi]$
Kết quả: ${dp}_{K} [N]$ .

Độ phức tạp

Thời gian: $O (N \log N + N \cdot K \cdot \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.

Bình luận

Không có bình luận tại thời điểm này.