F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 5164. -- 餐厅计划问题

5164: 餐厅计划问题

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 135  Solved: 37
[Submit][Status][Discuss]

Description

一个餐厅在相继的n天里,每天需用的餐巾数不尽相同。假设第i天(i=1,2,...,n)需要ri块餐巾。餐厅可以在任意
时刻购买新的餐巾,每块餐巾的费用为P。使用过的旧餐巾,则需要经过清洗才能重新使用。把一块旧餐巾送到清
洗店A,需要等待m1天后才能拿到新餐巾,其费用为c1;把一块旧餐巾送到清洗店B,需要等待m2天后才能拿到新餐
巾,其费用为c2。例如,将一块第k天使用过的餐巾送到清洗店A清洗,则可以在第k+m1天使用。请为餐厅合理地安
排好n天中餐巾使用计划,使总的花费最小。

Input

第一行,包含六个个正整数n,m1,m2,c1,c2,p
接下来输入n行,每行包含一个正整数ri。
1≤n≤200000,1≤m1,m2≤n,1≤c1,c2,p≤100,1≤ri≤100

Output

输出一行,包含一个正整数,表示最小的总花费

Sample Input

4 1 2 2 1 3
8
2
1
6

Sample Output

35
第1天:买8块餐巾,花费24。送2块餐巾去清洗店A,6块餐巾去清洗店B。
第2天:取回2块清洗店A的餐巾,花费4。送1块餐巾去清洗店B。
第3天:取回6块清洗店B的餐巾,花费6。
第4天:取回1块清洗店B的餐巾,花费1。这样就用了最少的钱。

HINT

Source

[Submit][Status][Discuss]

HOME Back