Description

\\n【题意】
\\r\\n贝西的生日快到了，她准备举办一个持续 $N$ 天的庆典。在庆典的第i天，她要为小伙伴们准备 $T_i$ 份玩具。
\\r\\n玩具可以从商店购买，每件 $P$ 元。
\\r\\n为了节约，在每天庆典结束之后，贝西会回收小伙伴用过的玩具，选择送全部或一部分玩具去消毒，经过消毒的玩具可以重复使用。
\\r\\n消毒店提供两种消毒方法，一种比较快，每件收费 $A$ 元，隔 $S$ 个夜晚能拿到；
\\r\\n另一种比较慢，每件收费只要 $B$ 元，但取货要隔 $T$ 个夜晚。
\\r\\n消毒后的玩具如果不立即使用，可以暂存起来。
\\r\\n请问贝西应该怎么做才能花最少的钱为小伙伴们提供玩具？
\\r\\n
\\r\\n【输入格式】
\\r\\n第一行：六个整数 $N，S，T，A，B，P$（$4 \\\\le N \\\\le 105,1 \\\\le S \\\\le T \\\\le N,1 \\\\le B \\\\le A \\\\le P \\\\le 60$）
\\r\\n第二行到第 $N+1$ 行：第 $i+1$ 行有一个整数 $T_i$ ($1 \\\\le T_i \\\\le 50$)
\\r\\n
\\r\\n【输出格式】
\\r\\n单个整数：表示为了提供玩具所需要的最小总费用
\\r\\n
\\r\\n【样例输入】
\\r\\n4 1 2 2 1 3
\\r\\n8
\\r\\n2
\\r\\n1
\\r\\n6
\\r\\n
\\r\\n【样例输出】
\\r\\n35
\\r\\n
\\r\\n【解释】
\\r\\n第一天买 8 份玩具，晚上送 2 件去快速消毒，6 件去慢速消毒；
\\r\\n第二天送 1 件去慢速消毒，最后两天不花钱 250
\\r\\n
\\r\\n【附注】
\\r\\n原题中没有说明快洗速度一定快于慢洗，且数据中有这样的数据，删去这些平凡的数据。
\\r\\n

统计

递交统计

*【最小割】玩具消毒P2917 [USACO08NOV] Toys G

信息

状态

开发

支持

关于

还没有账户？

登录