P1251 餐巾计划问题

    • 1.2K通过
    • 4.3K提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 网络流 贪心 网络流24题 O2优化 高性能
  • 难度 省选/NOI-
  • 时空限制 4000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    一个餐厅在相继的 $N$ 天里,每天需用的餐巾数不尽相同。假设第 $i$ 天需要 $r_i$块餐巾( i=1,2,...,N)。餐厅可以购买新的餐巾,每块餐巾的费用为 $p$ 分;或者把旧餐巾送到快洗部,洗一块需 m 天,其费用为 f 分;或者送到慢洗部,洗一块需 $n$ 天($n>m$),其费用为 $s$ 分($s<f$)。

    每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。

    试设计一个算法为餐厅合理地安排好 $N$ 天中餐巾使用计划,使总的花费最小。编程找出一个最佳餐巾使用计划。

    输入输出格式

    输入格式:

    由标准输入提供输入数据。文件第 1 行有 1 个正整数 $N$,代表要安排餐巾使用计划的天数。

    接下来的 $N$ 行是餐厅在相继的 $N$ 天里,每天需用的餐巾数。

    最后一行包含5个正整数$p,m,f,n,s$。$p$ 是每块新餐巾的费用; $m$ 是快洗部洗一块餐巾需用天数; $f$ 是快洗部洗一块餐巾需要的费用; $n$ 是慢洗部洗一块餐巾需用天数; $s$ 是慢洗部洗一块餐巾需要的费用。

    输出格式:

    将餐厅在相继的 N 天里使用餐巾的最小总花费输出

    输入输出样例

    输入样例#1: 复制
    3
    1 7 5 
    11 2 2 3 1
    
    输出样例#1: 复制
    134
    

    说明

    N<=2000

    ri<=10000000

    p,f,s<=10000

    时限4s

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。