Cải tạo vườn hoa

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ luống hoa xếp thành hàng ngang. Luống $i$ hiện chứa $A_{i}$ đơn vị đất, và cần chứa $B_{i}$ đơn vị đất. Ba thao tác được phép thực hiện:

Mua đất: thêm 1 đơn vị đất vào luống $i$ bất kỳ, chi phí $X$ đồng.
Bỏ đất: bỏ 1 đơn vị đất khỏi luống $i$ bất kỳ, chi phí $Y$ đồng.
Chuyển đất: chuyển 1 đơn vị đất từ luống $i$ sang luống $j$ , chi phí $Z \cdot | i - j |$ đồng.

Tìm tổng chi phí nhỏ nhất để đưa tất cả các luống về đúng lượng đất cần thiết.

Dòng $1$ : Bốn số nguyên $N$ , $X$ , $Y$ , $Z$ — số luống hoa và các chi phí tương ứng.
$N$ dòng tiếp theo: Mỗi dòng gồm hai số nguyên $A_{i}$ và $B_{i}$ .

Một số nguyên — tổng chi phí nhỏ nhất.

Input	Output	Giải thích
4 100 200 1 1 4 2 3 3 2 4 0	210	Chi phí mua đất = 100, bỏ đất = 200, chuyển đất = 1/đơn vị/vị trí. Phương án tối ưu: chuyển 1 đất từ luống 3 sang luống 2 (phí 1), chuyển 1 đất từ luống 4 sang luống 1 (phí 3), mua 2 đất cho luống 1 (phí 200), bỏ 1 đất từ luống 4 (phí 200)... Tổng = 210.
20 12 11 1 10 3 1 3 4 8 6 10 3 3 9 10 8 4 7 2 3 10 4 2 10 5 8 9 5 6 1 4 7 2 1 7 4 3 1 7 2 6 6 5	157	Với $N = 20$ luống, chi phí mua = 12, bỏ = 11, chuyển = 1/bước. Kết hợp tối ưu các thao tác cho tổng chi phí = 157.

Bình luận

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