houses_schools

Bài Houses and Schools: đặt $k=2$ trường học vào $n=6$ ngôi nhà sao cho tổng quãng đường đi bộ nhỏ nhất. Số trẻ em: $[2, 3, 5, 1, 4, 6]$. Ta xây dựng $dp[j][i]$ = chi phí nhỏ nhất khi dùng $j$ trường cho các nhà $1..i$.

Trường hợp cơ sở: $dp[0][0] = 0$. Không trường nào phục vụ không nhà nào thì chi phí bằng $0$. Tất cả $dp[0][i]$ khác đều là vô cực (không thể phục vụ nhà nào mà không có trường).

$dp[1][1] = cost(1,1) = 0$. Một trường tại nhà $1$ chỉ phục vụ nhà $1$. Không cần đi bộ.

$dp[1][2] = cost(1,2) = 2$. Một trường cho nhà $1$-$2$: trung vị có trọng số tại nhà $2$ (trọng số $3 \geq$ nửa của $5$). Chi phí $= 2 \times 1 + 3 \times 0 = 2$.

$dp[1][3] = cost(1,3) = 7$. Trung vị có trọng số tại nhà $3$. Chi phí $= 2 \times 2 + 3 \times 1 + 5 \times 0 = 7$.

$dp[1][4] = cost(1,4) = 8$. Trung vị vẫn tại nhà $3$ (trọng số tích lũy $10 \geq 5.5$). Chi phí $= 2 \times 2 + 3 \times 1 + 5 \times 0 + 1 \times 1 = 8$.

$dp[1][5] = cost(1,5) = 16$. Trung vị tại nhà $3$. Chi phí $= 2 \times 2 + 3 \times 1 + 5 \times 0 + 1 \times 1 + 4 \times 2 = 16$. Thêm nhà $5$ ở xa làm chi phí tăng đáng kể.

$dp[1][6] = cost(1,6) = 33$. Trung vị dịch sang nhà $4$. Chi phí $= 2 \times 3 + 3 \times 2 + 5 \times 1 + 1 \times 0 + 4 \times 1 + 6 \times 2 = 33$. Một trường cho tất cả các nhà rất tốn kém!

Hàng $j=1$ hoàn thành. Với một trường, chi phí tăng nhanh khi đoạn mở rộng. Bây giờ ta tính hàng $j=2$: đặt hai trường. Công thức truy hồi là $dp[2][i] = \min_m (dp[1][m] + cost(m+1, i))$.

$dp[2][2] = dp[1][1] + cost(2,2) = 0 + 0 = 0$. Chia tại $m=1$: trường thứ nhất phục vụ nhà $1$, trường thứ hai phục vụ nhà $2$. Cả hai đều không cần đi bộ.

$dp[2][3]$: thử $m=1$: $dp[1][1] + cost(2,3) = 0 + 3 = 3$ (trung vị tại $3$, chi phí $= 3 \times 1 + 5 \times 0 = 3$). Thử $m=2$: $dp[1][2] + cost(3,3) = 2 + 0 = 2$. Tốt nhất là $m=2$.

$dp[2][3] = 2$. Chia tối ưu: trường thứ nhất phục vụ nhà $1$-$2$ (chi phí $2$), trường thứ hai tại nhà $3$ (chi phí $0$). Tối ưu chia để trị khai thác tính đơn điệu của $opt(j,i)$.

$dp[2][4]$: thử $m=1$ cho $4$, $m=2$ cho $dp[1][2]+cost(3,4) = 2+1 = 3$ (trung vị tại $3$, chi phí $= 5 \times 0 + 1 \times 1 = 1$), $m=3$ cho $7$. Tốt nhất tại $m=2$.

$dp[2][4] = 3$. Chia tại $m=2$: trường $1$ phục vụ nhà $1$-$2$ (chi phí $2$), trường $2$ phục vụ nhà $3$-$4$ (chi phí $1$). Tính đơn điệu được giữ: $opt(2,4) = 2 \geq opt(2,3) = 2$.

$dp[2][5]$: $m=3$ cho $dp[1][3]+cost(4,5) = 7+1 = 8$ (trường tại $5$, chi phí $= 1 \times 1 + 4 \times 0 = 1$). $m=4$ cũng cho $8+0=8$. Tốt nhất là $8$.

$dp[2][5] = 8$. Với $2$ trường cho $5$ nhà, chia tại $m=3$ hay $m=4$ đều cho chi phí $8$. Điểm chia tối ưu đã dịch sang phải, xác nhận tính đơn điệu.

$dp[2][6]$: $m=4$ cho $dp[1][4]+cost(5,6) = 8+4 = 12$ (trường tại $6$, chi phí $= 4 \times 1 + 6 \times 0 = 4$). Các cách chia khác: $m=3$ cho $13$, $m=5$ cho $16$. Tốt nhất tại $m=4$.

$dp[2][6] = 12$. Chia tại $m=4$: trường $1$ tại nhà $3$ phục vụ nhà $1$-$4$ (chi phí $8$), trường $2$ tại nhà $6$ phục vụ nhà $5$-$6$ (chi phí $4$). Tổng $= 12$.

Đáp án: $dp[2][6] = 12$. Trường đặt tại nhà $3$ và nhà $6$. Không có tối ưu chia để trị thì mất $O(kn^2)$. Nhờ tính đơn điệu của opt, mỗi hàng giải trong $O(n \log n)$, tổng cộng $O(kn \log n)$. Với $n=3000$, đó là sự khác biệt giữa TLE và AC.