#P1221. [HNOI2001] 软件开发

    ID: 229 传统题 1000ms 162MiB 尝试: 2218 已通过: 948 难度: 7 上传者: 标签>CF2200提高+/省选-指定流量最小费用流供需平衡建模势能优化费用流Dijkstra费用流

[HNOI2001] 软件开发

题目描述

某软件公司正在规划一项 nn 天的软件开发计划,根据开发计划第 ii 天需要 nin_i 个软件开发人员,为了提高软件开发人员的效率,公司给软件人员提供了很多的服务,其中一项服务就是要为每个开发人员每天提供一块消毒毛巾,这种消毒毛巾使用一天后必须再做消毒处理后才能使用。

消毒方式有两种,AA 种方式的消毒需要 aa 天时间,BB 种方式的消毒需要 bb 天,AA 种消毒方式的费用为每块毛巾 fAf_A, BB 种消毒方式的费用为每块毛巾 fBf_B,而买一块新毛巾的费用为 ff(新毛巾是已消毒的,当天可以使用)。公司经理正在规划在这 nn 天中,每天买多少块新毛巾、每天送多少块毛巾进行 AA 种消毒和每天送多少块毛巾进行 BB 种消毒。当然,公司经理希望费用最低。

你的任务就是:为该软件公司计划每天买多少块毛巾、每天多少块毛巾进行 AA 种消毒和多少毛巾进行 BB 种消毒,使公司在这项 nn 天的软件开发中,提供毛巾服务的总费用最低。

输入格式

第一行为六个整数 n,a,b,f,fA,fBn,a,b,f,f_A,f_B。

第二行为 nn 个整数 n1,n2,…,nnn_1,n_2,\ldots,n_n。

输出格式

仅一个整数,为最少的费用。

样例 #1

样例输入 #1

4  1  2  3  2  1                         
8  2  1  6

样例输出 #1

38

提示

数据规模与约定

对于 100%100\% 的数据,保证 b>ab>a,f>fA>fBf>f_A>f_B,1≤f,fA,fB≤601\le f,f_A,f_B\le 60,1≤n≤1031\le n\le 10^3。

本站当前数据版本的需求范围

每日需求 nin_i 是非负整数。本站当前安装的10组原测试已经全部核验,每日需求均不超过100,当前数据版本明确采用 0≤ni≤1000\le n_i\le100。这项界限是本站当前测试材料的补充,不冒称原始HNOI题面已有该保证。费用参数沿用题面,其总费用可使用64位有符号整数计算;费用流边容量可取所有需求之和,不能无依据固定为一个较小常数。