网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[网络流24题]餐巾
成绩 | 开启时间 | 2014年09月19日 星期五 10:05 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:05 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:05 |
输入文件 | napkin.in | 输出文件 | napkin.out |
【问题描述】
一个餐厅在相继的N天里,第i天需要Ri块餐巾(i=l,2,…,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