[网络流24题]餐巾

Grade Open Time Friday, 19 September 2014, 10:05 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:05 am
Allow late Yes Close Time Friday, 26 September 2014, 10:05 am
Input file napkin.in Output file napkin.out

【问题描述】


 一个餐厅在相继的N天里,第i天需要Ri块餐巾(i=l2,…,N)。餐厅可以从三种途径获得餐巾。

    (1)购买新的餐巾,每块需p分;

    (2)把用过的餐巾送到快洗部,洗一块需m天,费用需f分(f<p)。如m=l时,第一天送到快洗部的餐巾第二天就可以使用了,送慢洗的情况也如此。

    (3)把餐巾送到慢洗部,洗一块需n天(n>m),费用需s分(s<f)。

    在每天结束时,餐厅必须决定多少块用过的餐巾送到快洗部,多少块送慢洗部。在每天开始时,餐厅必须决定是否购买新餐巾及多少,使洗好的和新购的餐巾之和满足当天的需求量Ri,并使N天总的费用最小。



【输入】

输入文件共 3 行,第 1 行为总天教;第 2 行为每天所需的餐巾块数;第 3 行为每块餐巾的新购费用 p ,快洗所需天数 m ,快洗所需费用 f ,慢洗所需天数 n ,慢洗所需费用 s 。

【输出】

一行,最小的费用

【样例】

napkin.in

3
3 2 4
10 1 6 2 3

napkin.out

64

【数据规模】

n<=200,Ri<=50