Cột điện

Nguồn: CLUE OJ – Chương 22: Quy hoạch động Độ khó: Khá QHĐ theo trạng thái chiều cao Min tiền tố

Đề bài

Công ty điện lực của Tý có nhiệm vụ cung cấp điện cho thành phố X. Để cung cấp điện cho thành phố công ty đã cho lắp đặt một hệ thống gồm $n$ cột điện được đánh số theo thứ tự từ $1$ đến $n$, cột điện thứ $i$ có chiều cao là một số nguyên dương $h_i$, các dây điện được nối giữa các cột liền kề, tức là nối từ cột 1 đến cột 2, từ cột 2 đến cột 3, …, từ cột $n - 1$ đến cột $n$.

Vì mỹ quan đô thị, Lãnh đạo hòn đảo đã đưa ra quy định sẽ thu công ty của Tý một khoản chi phí cho hai cột điện liền kề $i$ và $i + 1$ là $c \times |h_i - h_{i+1}|$ ($c$ là giá chi phí cho mỗi đơn vị chênh lệch chiều cao giữa 2 cột điện liền kề), tổng chi phí là $S = c \times \sum_{i=1}^{n-1} |h_i - h_{i+1}|$. Để giảm thiểu chi phí, lãnh đạo công ty đã quyết định chọn giải pháp cho lắp đặt nâng chiều cao một số cột điện. Tuy nhiên, nếu cột điện $i$ nâng chiều cao thêm $x$ (đơn vị) thì công ty phải mất một khoản chi phí là $x^2$.

Yêu cầu: cho biết $n, c$ và các chiều cao $h_i$ $(i = 1..n)$, bạn hãy giúp công ty của Tý tính chi phí $S$ thấp nhất khi công ty thực hiện theo giải pháp của lãnh đạo công ty.

Dữ liệu vào: đọc vào từ file văn bản POLE.INP gồm:

• Dòng đầu tiên chứa hai số nguyên $n, c$ $(1 \le n \le 10^4,\ 1 \le c \le 10^6)$;
• Mỗi dòng trong $n$ dòng sau chứa một số nguyên $h_i$ $(1 \le h_i \le 1000)$.
• Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách.

Kết quả: đưa ra file văn bản POLE.OUT một số nguyên là chi phí thấp nhất mà công ty của Tý phải trả (gồm cả chi phí nâng cột và chi phí chênh lệch).

Ràng buộc:

• Subtask 1: có 25% số test tương ứng 0.5 điểm với $n \le 10$ và $h_i \le 3$;
• Subtask 2: có 25% số test tương ứng 0.5 điểm với $n \le 1000$ và $h_i \le 100$;
• Subtask 3: có 50% số test tương ứng 1.0 điểm với $n \le 10000$ và $h_i \le 1000$.

Ví dụ – input

5 2
2
3
5
1
4

Ví dụ – output

15

Giải thích ví dụ: nâng cột 1 thêm 1, nâng cột 4 thêm 2. Khi đó chiều cao các cột lần lượt là $3, 3, 5, 3, 4$. Tổng chi phí là $2 \times (0 + 2 + 2 + 1) + 1^2 + 2^2 = 15$.

Lưu ý khi nộp bài: đề yêu cầu đọc/ghi file POLE.INP / POLE.OUT. Code bên dưới dùng if(fopen("POLE.INP", "r")) để nếu có file thì đọc file, còn không thì đọc bàn phím – nộp trên CLUE OJ hay Codeforces đều chạy được.

Lời mở đầu

Mỗi cột chỉ được nâng lên chứ không được hạ xuống, nâng càng nhiều càng tốn ($x^2$) nhưng bù lại có thể làm "phẳng" đường dây để giảm phần $c \times |h_i - h_{i+1}|$. Đây là dạng QHĐ rất hay gặp: trạng thái gồm vị trí và giá trị (cột thứ $i$ cao bao nhiêu). Mình sẽ đi từ quay lui thử mọi chiều cao (subtask 1), sang QHĐ $O(n \cdot H^2)$ (subtask 2), rồi dùng kỹ thuật min tiền tố / hậu tố để bỏ bớt một chiều, ăn trọn 100%.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Dành cho tất cả mọi ngườiNộp bài trên Codeforces

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.

Nộp bài trên Codeforces

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test15 testCách 1Quay luiÝ tưởngBảng f[i][x]Cách 2O(nH²)Cách 3O(nH) 100%

Bộ testBộ test chính thức có gì?

Test	$n$	$c$	$h_i$	Đáp án lớn nhất
1–5	4 … 9	50 … 60.768	1 … 3	11
6–10	509 … 1.000	38 … 992	1 … 100	2.229.189
11–15	5.364 … 10.000	41 … 87.696	1 … 1000	2.677.040.398

Bộ test chỉ có 15 test, chia đều 5 test cho mỗi subtask (đề ghi tỉ lệ điểm 25% – 25% – 50%, còn số test là 5 – 5 – 5). Đáp án lớn nhất là 2.677.040.398 > $2^{31} - 1$ (test 12, $c = 87\,696$), nên chi phí phải lưu bằng long long.

Subtask	Điều kiện	Test	Cách 1 (quay lui)	Cách 2 (QHĐ $O(nH^2)$)	Cách 3 (QHĐ $O(nH)$)
1	$n \le 10$, $h_i \le 3$	1–5	qua	qua	qua
2	$n \le 1000$, $h_i \le 100$	6–10	quá thời gian	qua	qua
3	$n \le 10^4$, $h_i \le 1000$	11–15	quá thời gian	quá thời gian	qua

Cách 1Quay lui thử mọi chiều cao (subtask 1)

Gọi $H = \max h_i$. Nhận xét đầu tiên: không bao giờ có lợi khi nâng một cột cao hơn $H$. Thật vậy, nếu có cột cao hơn $H$, ta "cắt" mọi cột cao hơn $H$ xuống đúng $H$: chi phí nâng giảm, và chênh lệch giữa 2 cột kề nhau không tăng (vì $|\min(a, H) - \min(b, H)| \le |a - b|$). Vậy cột $i$ chỉ nhận chiều cao mới trong đoạn $[h_i, H]$.

Với subtask 1, $H \le 3$, mỗi cột có tối đa 3 lựa chọn, $n \le 10$ cột → tối đa $3^{10} = 59\,049$ cách – thử hết bằng đệ quy Try(i, cost): chọn chiều cao $v$ cho cột $i$, cộng chi phí nâng $(v - h_i)^2$ và chi phí dây với cột $i - 1$, rồi gọi tiếp cột $i + 1$.

C++▶ Chạy tay từng dòng codeCách 1: Try(i, cost) thử mọi chiều cao v trong [h[i], H] cho cột i.

Dữ liệu vào (stdin) – sửa thoải mái3 2 1 3 2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Ví dụ của đề có 120 cách chọn chiều cao nên mình dùng các bộ nhỏ hơn (n ≤ 4, h ≤ 3 – đúng giới hạn subtask 1). Khung phải là ngăn xếp lời gọi.

Không gian$O(n)$ (độ sâu đệ quy)

Thời gian$O(H^n)$

Kết quả chạy thật: bản C++ đúng 5/15 test – trọn subtask 1, mỗi test dưới 0,01 giây; bản Python cũng qua 5 test này (0,02 giây). Từ test 6 ($H$ = 100, $n$ tới 1000) số cách là $100^{1000}$ – quá thời gian ở cả 10 test còn lại.

Ý tưởng QHĐBảng $f[i][x]$: cột $i$ cao đúng $x$

Trong cây quay lui, khi đã quyết định xong cột $i$ cao $x$, phần chi phí phía sau chỉ phụ thuộc vào $x$, không phụ thuộc các cột trước cao bao nhiêu. Vậy ta chỉ cần nhớ chi phí nhỏ nhất cho mỗi cặp (cột $i$, chiều cao $x$):

Công thức QHĐ

$f[i][x]$ = chi phí nhỏ nhất cho các cột $1..i$ khi cột $i$ được nâng lên đúng chiều cao $x$ ($h_i \le x \le H$). $$f[1][x] = (x - h_1)^2, \qquad f[i][x] = (x - h_i)^2 + \min_{h_{i-1} \le y \le H} \big( f[i-1][y] + c \cdot |x - y| \big)$$ Đáp án $= \min_x f[n][x]$.

Em nhập $c$ và các chiều cao rồi bấm Tiếp. Mỗi bước tính một ô $f[i][x]$: các ô xanh tím ở hàng trên là các $f[i-1][y]$ được thử, ô viền tím đậm là $y$ tốt nhất. Bước cuối lần ngược ra chiều cao mới của từng cột:

ô đang tínhcác f[i−1][y] được thửy tốt nhấtphương án tối ưu (bước cuối)

c Chiều cao h

Ví dụ nhanh:

Cách 2QHĐ $O(n \cdot H^2)$ (subtask 1, 2)

Cài đặt thẳng công thức trên. Vì hàng $i$ chỉ cần hàng $i - 1$, mình chỉ giữ 2 hàng f[0], f[1] và dùng i & 1 để luân phiên (hàng hiện tại cur, hàng trước pre).

C++▶ Chạy tay từng dòng codeCách 2: f[cur][x] = (x − h[i])² + min theo y của f[pre][y] + c·|x − y|.

Dữ liệu vào (stdin) – sửa thoải mái5 2 2 3 5 1 4

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Gộp dòng for y vào dòng cập nhật min bên trong. Ô vàng: f[cur][x] đang tính, ô xanh tím: f[pre][y] đang thử.

1. Các ô $x < h_i$ gán INF (không được hạ cột). Chọn INF = LLONG_MAX / 4 để cộng thêm $c \cdot |x - y|$ không bị tràn.
2. Ba vòng lặp lồng nhau: $n \cdot H \cdot H$. Subtask 2: $1000 \cdot 100 \cdot 100 = 10^7$ – rất nhanh. Subtask 3: $10^4 \cdot 1000 \cdot 1000 = 10^{10}$ – quá chậm.

Không gian$O(H)$ (2 hàng)

Thời gian$O(n \cdot H^2)$

Kết quả chạy thật: bản C++ đúng 10/15 test (subtask 1, 2), 5 test subtask 3 chạy 1,5–2,7 giây → quá thời gian. Bản Python qua 10 test đầu, chậm nhất 0,28 giây.

Cách 3Bỏ vòng lặp $y$ bằng min tiền tố / hậu tố (full điểm)

Phần đắt nhất là $\min_y \big(f[i-1][y] + c|x - y|\big)$. Ta tách dấu giá trị tuyệt đối theo 2 trường hợp:

• $y \le x$: $f[i-1][y] + c(x - y)$ $= \big(f[i-1][y] - c \cdot y\big)$ $+ c \cdot x$.
• $y \ge x$: $f[i-1][y] + c(y - x)$ $= \big(f[i-1][y] + c \cdot y\big) - c \cdot x$.

Phần trong ngoặc không phụ thuộc $x$! Nên ta tính trước 2 mảng:

Min tiền tố và min hậu tố

$L[x] = \min_{y \le x} \big(f[i-1][y] - c y\big)$ (tính từ trái sang phải), $\quad R[x]$ $= \min_{y \ge x} \big(f[i-1][y] + c y\big)$ (tính từ phải sang trái). $$f[i][x] = (x - h_i)^2 + \min\big(L[x] + c x,\ R[x] - c x\big)$$

Mỗi hàng giờ chỉ tốn $O(H)$, cả bài $O(n \cdot H) = 10^4 \cdot 1000 = 10^7$ phép tính.

C++▶ Chạy tay từng dòng codeCách 3: min tiền tố L và min hậu tố R giúp tính mỗi hàng trong O(H).

Dữ liệu vào (stdin) – sửa thoải mái5 2 2 3 5 1 4

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Bốn hàng: f (cột trước), L (min tiền tố của f − c·y), R (min hậu tố của f + c·y), g (cột hiện tại).

1. Ô có f[x] = INF (chiều cao không hợp lệ) không được tham gia min – mình giữ nguyên INF thay vì trừ $c \cdot x$ để khỏi tạo ra số "giả" nhỏ hơn.
2. Mảng g là hàng mới, chép lại vào f cuối mỗi vòng – bộ nhớ chỉ $O(H)$.

Không gian$O(H)$

Thời gian$O(n \cdot H)$

Kết quả chạy thật: bản C++ đúng 15/15 test, chậm nhất 0,039 giây. Bản Python cùng thuật toán (mình đã dùng itertools.accumulate để tính min tiền tố cho nhanh) vẫn cần $10^4 \times 1000 \times 4$ phép tính trên list, chạy khoảng 1,6–1,8 giây ở 5 test lớn nên chỉ được 10/15 – Python không kịp 1 giây ở subtask 3.

Ghi chú của mình: C++: cách 1 (quay lui) 5/15, cách 2 (QHĐ $O(nH^2)$) 10/15, cách 3 (QHĐ + min tiền tố/hậu tố $O(nH)$) 15/15 – chậm nhất 0,039 giây. Python: cách 3 chỉ 10/15 vì quá thời gian ở subtask 3. Nhớ dùng long long: đáp án test 12 là 2.677.040.398, vượt int.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇