P2917 [USACO08NOV]玩具Toys

    • 66通过
    • 201提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 状态压缩,状压 生成树 贪心 USACO 2008 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    Bessie's birthday is coming up, and she wishes to celebrate for the next D (1 <= D <= 100,000; 70% of testdata has 1 <= D <= 500) days. Cows have short attention spans so Bessie wants to provide toys to entertain them. She has calculated that she will require T_i (1 <= T_i <= 50) toys on day i.

    Bessie's kindergarten provides many services to its aspiring bovine programmers, including a toy shop which sells toys for Tc (1 <= Tc <= 60) dollars. Bessie wishes to save money by reusing toys, but Farmer John is worried about transmitting diseases and requires toys to be disinfected before use. (The toy shop disinfects the toys when it sells them.)

    The two disinfectant services near the farm provide handy complete services. The first one charges C1 dollars and requires N1 nights to complete; the second charges C2 dollars and requires N2 nights to complete (1 <= N1 <= D; 1 <= N2 <= D; 1 <= C1 <= 60; 1 <= C2 <= 60). Bessie takes the toys to the disinfecters after the party and can pay and pick them back up the next morning if one night service is rendered, or on later mornings if more nights are required for disinfecting.

    Being an educated cow, Bessie has already learned the value of saving her money. Help her find the cheapest way she can provide toys for her party.

    POINTS: 400

    Bessie的生日快到了,她希望用D(1<=D<=100000)天来庆祝。奶牛们的注意力不会太集中,因此Bessie想通过提供玩具的方式来使它们高兴。她已经计算出了第i天需要的玩具数Ti(1<=Ti<=50).

    Bessie的幼儿园给它们的奶牛程序员们提供了许多服务,包括一个每天以Tc(1<=Tc<=60)美元卖出商品的玩具店。Bessie想尽可能地节省钱。但是Farmer John担心没有经过消毒的玩具会带来传染病。(玩具店卖出的玩具是经过消毒)

    有两种消毒的方式。第1种方式需要收费C1美元,需要N1个晚上的时间;第2种方式需要收费C2美元,需要N2个晚上的时间(1<=N1,N2<=D;1<=C1,C2<=60)。Bessie在派对结束之后把她的玩具带去消毒。如果消毒只需要一天,那么第二天就可以拿到;如果还需要一天,那么第三天才可以拿到。

    作为一个受过教育的奶牛,Bessie已经了解到节约的意义。帮助她找到提供玩具的最便宜的方法。

    输入输出格式

    输入格式:

    * Line 1: Six space-separated integers: D, N1, N2, C1, C2, Tc

    * Lines 2..D+1: Line i+1 contains a single integer: T_i

    输出格式:

    * Line 1: The minimum cost to provide safe and sanitary toys for Bessie's birthday parties.

    输入输出样例

    输入样例#1: 复制
    4 1 2 2 1 3 
    8 
    2 
    1 
    6 
    
    输出样例#1: 复制
    35 
    

    说明

    Bessie wishes to party for 4 days, and requires 8 toys the first day, 2 toys the second, 1 toy the third, and 6 toys on the fourth day. The first disinfectant service takes 1 day and charges $2, and the second takes 2 days and charges $ 1. Buying a new toy costs $3.

    Day 1 Purchase 8 toys in the morning for $24; party in the

    afternoon. Take 2 toys to the fast cleaner (overnight) and

    the other 6 toys to the slow cleaner (two nights).

    Day 2 Pick up the two toys at the fast cleaner; pay $4. Party in the afternoon. Take 1 toy to the slow cleaner.

    Day 3 Pick up 6 toys from the slow cleaner and pay $6. Party in the afternoon.

    Day 4 Pick up the final remaining toy from the slow cleaner

    (bringing the number of toys onsite back to 6); pay $1. Party hearty with the realization that a minimum amount of money was spent.

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