1495 - THUÊ XE
Tạo bởi: GV. Bùi Phú Khuyên
Mô tả yêu cầu
Để đảm bảo tất cả các bạn sinh viên K23 đều được đi tham quan doanh nghiệp theo chương trình HUTECH IT OFFICE TOUR, Khoa Công nghệ thông tin cần phải thuê đúng A_1, A_2,… , A_n các xe Bus cho N buổi liên tiếp đánh số từ 1…n.
Cô Trang đã liên hệ với các đơn vị vận tải để thuê xe, và có 3 gói lựa chọn của đơn vị cung cấp các chuyến xe như sau:
- Lựa chọn 1: Giá thuê 1 xe là X đồng/ 1 ngày.
- Lựa chọn 2: Giá thuê 1 xe là Y đồng/ 1 ngày, nhưng phải thuê ít nhất 2 ngày.
- Lựa chọn 3: Giá thuê 1 xe là Z đồng/ 1 ngày, nhưng phải thuê đủ N ngày.
Biết rằng X > Y > Z. Hãy giúp Cô Trang tính tổng chi phí nhỏ nhất để có thể thuê đủ xe cho N ngày?
Dữ liệu vào
- Dòng 1: Chứa 3 Số nguyên: N X Y Z cách nhau bằng khoảng trắng
- Dòng 2: Chứa N số nguyên dương A_1, A_2, … , A_n cách nhau bằng khoảng trắng
Dữ liệu ra
Tổng chi phí nhỏ nhất tìm được.
Ví dụ
| Dữ liệu vào Sao chép |
3 10 8 6 6 4 8 |
| Dữ liệu ra Sao chép |
124 |
Gợi ý/Hướng dẫn
- Thuê 4 xe (lựa chọn 3) ở 3 ngày (1, 2, 3) với giá 4 × 3 × 6 = 72.
- Thuê 2 xe (lựa chọn 2) ở 2 ngày (1, 3) với giá: 2 × 2 × 8 = 32.
- Thuê 2 xe (lựa chọn 1) ở 1 ngày (3) với giá: 2 × 10 = 20.
- Tổng số tiền: 72 + 32 + 20 = 124.
Đăng nhập để làm bài