Đồ chơi

Điểm: 1,51 (OI)

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

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

Input: stdin

Output: stdout

Nguồn bài:

USACO November 2008

Dạng bài

Ngôn ngữ cho phép

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

Ngày sinh nhật của cô bò Bessie đang đến, cô muốn mừng sinh nhật trong ~D~ ngày sắp tới.

Đàn bò ít chú ý nên Bessie muốn có các đồ chơi để góp vui cho buổi tiệc. Cô đã tính toán rằng cần phải có ~T_i~ đồ chơi trong ngày ~i~.

Trường mẫu giáo của Bessie có rất nhiều dịch vụ cho các lập trình viên bò, trong đó có một cửa hàng đồ chơi bán đồ chơi với giá ~T_c~ đô-la. Bessie muốn tiết kiệm tiền bằng cách dùng lại đồ chơi, nhưng bác John lo về nguy cơ lây nhiễm COVID-19 nên yêu cầu các đồ chơi phải được khử trùng trước khi sử dụng (cửa hàng sẽ khử trùng đồ chơi khi bán chúng).

Có hai dịch vụ khử trùng gần trang trại. Dịch vụ thứ nhất đòi ~C_1~ đô-la và cần ~N_1~ đêm để hoàn thành. Dịch vụ thứ hai đòi ~C_2~ dollars và cần ~N_2~ đêm để hoàn thành.

Bessie đem đồ chơi đến các dịch vụ này sau buổi tiệc và có thể trả tiền đồng thời lấy đồ chơi về vào buổi sáng hôm sau nếu dịch vụ cần một đêm để làm việc, hoặc trong các buổi sáng sau, nếu dịch vụ cần nhiều đêm hơn.

Hãy tính chi phí ít nhất để Bessie chuẩn bị đồ chơi cho sinh nhật của cô.

Input

Dòng đầu chứa ~6~ số nguyên dương: ~D \leq 10^5, N_1 \leq D, N_2 \leq D, C_1 \leq 60, C_2 \leq 60, T_c \leq 60~.

Sau đó là ~D~ dòng, mỗi dòng chứa một số nguyên dương ~T_i \leq 60~

Output

In ra chi phí ít nhất.

Giới hạn

Có ~75\%~ số test ứng với ~75\%~ số điểm của bài có ~D \leq 500~.
~25\%~ số test còn lại không có giới hạn gì thêm.

Sample Input

4 1 2 2 1 3
8
2
1
6

Sample Output

Bình luận

Hãy đọc nội quy trước khi bình luận.

1

_noob đã bình luận lúc 12, Tháng 1, 2025, 5:11

Đầu tiên nhận xét rằng nếu 1 dịch vụ tốt hơn hẳn thì sẽ luôn chọn dịch vụ đó (~N_1 < N_2~ và ~C_1 < C_2~)

Nếu vậy thì bài toán dễ, chúng ta sẽ xử lí TH khó hơn là ~N_1 > N_2~ và ~C_1 < C_2~

Coi như chúng ta sẽ mua hết đồ chơi ở ban đầu, vì sau này mua hay ban đầu mua cũng như nhau. Giả sử chúng ta mua ~x~ đồ chơi:

Khi đến ngày ~i~ nếu như mà không đủ đồ chơi thì đồ chơi ở một vài trước đó phải được đem đi rửa

Chúng ta sẽ ưu tiên lấy đồ chơi ở ngày xa ngày ~i~ nhất đi rửa vì như đã giả sử ở trên thì ngày càng xa thì tiền càng ít

Ở đây sẽ có ~3~ deque để quản lí đồ chơi của ngày nào trong khoảng từ ~i - N_2 \rightarrow i - 1~, ~i - N_1 + 1 \rightarrow i - N_2 - 1~, ~1 \rightarrow i - N_1~, lần lượt tượng trưng cho chưa thể lấy vì chưa rửa xong, có thể lấy với giá là ~C_2~, có thể lấy với giá ~C_1~.

Từ đó nhận thức được rằng sẽ luôn ưu tiên lấy ở phần thứ ba trước, sau đó mới lấy ở phần thứ hai. Tuy nhiên lúc lấy ở phần thứ 2 phải lưu ý rằng lấy từ thằng gần ~i~ nhất để những thằng xa ~i~ có khả năng chuyển sang phần thứ ba để tiết kiệm hơn.

Gọi ~f(x)~ là giá trị ít nhất để hoàn thành với số lượng đồ chơi ban đầu là ~x~

Thấy rằng f(x) là một hàm lồi. Có thể hiểu đơn giản là nếu như chưa đủ số lượng thì ~f(x) = \infty~, đến một ngưỡng nào đó thì đã đủ để hoàn thành tuy nhiên số lần rửa còn rất nhiều. Sau đó hàm sẽ giảm đến cực tiểu rồi tăng dần. Do giả sử ~best~ là vị trí tối ưu nhất, thì những số lớn hơn best chỉ đơn giản là áp dụng cách tương tự chỉ là số lượng cho ban đầu lớn hơn => tăng dần.

Phần chứng minh toán học có thể để bạn đọc tự chứng minh

Áp dụng chặt tam phân

Code tham khảo

1

esciihere đã bình luận lúc 29, Tháng 3, 2024, 6:51

what the hell

-7

Codeforfun đã bình luận lúc 8, Tháng 1, 2023, 6:24

:)))

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.