题目名称	461. [网络流24题] 餐巾
输入输出	`napkin.in/out`
难度等级	★★★☆
时间限制	5000 ms (5 s)
内存限制	512 MiB
测试数据	12
题目来源	cqw 于2010-09-13加入
开放分组	全部用户
提交状态
分类标签	动态规划贪心网络流三分法
查看题解	分享题解

通过：348，提交：653，通过率：53.29%
~玖湫~	100	0.000 s	0.00 MiB	C++
Youngsc	100	0.000 s	0.00 MiB	C++
Hzoi_QTY	100	0.000 s	0.08 MiB	C++
AAAAAAAAAA	100	0.000 s	0.24 MiB	C++
Hzoi_Mafia	100	0.001 s	0.10 MiB	C++
Hzoi_Mafia	100	0.002 s	0.10 MiB	C++
jhs	100	0.002 s	0.84 MiB	C++
HZOI_蒟蒻一只	100	0.003 s	0.08 MiB	C++
面对疾风吧疾风疾风吧	100	0.003 s	0.32 MiB	C++
scy_666	100	0.003 s	0.37 MiB	C++

本题关联比赛
20100913

关于餐巾的近10条评论(全部评论)
还是费用流打的不熟啊...白痴错误查了2节课 CSU_Turkey 2018-01-02 15:09 25楼
回复 @Hallmeow : 蛤蛤蛤？ ---update--- mdzz stdin&stdout写错了 WA了一次一脸茫然 Hzoi_Mafia 2017-07-31 09:06 24楼
皮皮星收好 Hallmeow 2017-07-31 08:47 23楼
拆点这个东西……比较玄学…… HZOI_蒟蒻一只 2017-07-30 21:00 22楼
建图很强看学长的课件 하루Kiev 2017-07-29 17:53 21楼
xyz117 2017-07-29 11:19 20楼
这道题的建图好神奇啊。。。。但是我还是一脸懵逼。。。。。 HeHe 2017-04-10 17:48 19楼
神建图 Rapiz 2017-03-05 19:06 18楼
噫，竟然0.035s过，话说前几名是如何做到0.003s？ infinityedge 2017-02-05 09:56 17楼
zkw速度快赶上三分了 _Itachi 2017-01-09 07:22 16楼

461. [网络流24题] 餐巾

★★★☆ 输入文件：napkin.in 输出文件：napkin.out 简单对比
时间限制：5 s 内存限制：512 MiB

【问题描述】

一个餐厅在相继的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 。

【输出格式】

一行，最小的费用

【输入样例】

3
3 2 4
10 1 6 2 3

【输出样例】

【数据规模】

n<=200,Ri<=50