2 shunfurh shunfurh 于 2017.01.15 11:56 提问

Alice's mooncake shop

Description

The Mid-Autumn Festival, also known as the Moon Festival or Zhongqiu Festival is a popular harvest festival celebrated by Chinese people, dating back over 3,000 years to moon worship in China's Shang Dynasty. The Zhongqiu Festival is held on the 15th day of the eighth month in the Chinese calendar, which is in September or early October in the Gregorian calendar. It is a date that parallels the autumnal equinox of the solar calendar, when the moon is at its fullest and roundest.

The traditional food of this festival is the mooncake. Chinese family members and friends will gather to admire the bright mid-autumn harvest moon, and eat mooncakes under the moon together. In Chinese, “round”(圆) also means something like “faultless” or “reuion”, so the roundest moon, and the round mooncakes make the Zhongqiu Festival a day of family reunion.

Alice has opened up a 24-hour mooncake shop. She always gets a lot of orders. Only when the time is K o’clock sharp( K = 0,1,2 …. 23) she can make mooncakes, and We assume that making cakes takes no time. Due to the fluctuation of the price of the ingredients, the cost of a mooncake varies from hour to hour. She can make mooncakes when the order comes,or she can make mooncakes earlier than needed and store them in a fridge. The cost to store a mooncake for an hour is S and the storage life of a mooncake is T hours. She now asks you for help to work out a plan to minimize the cost to fulfill the orders.
Input

The input contains no more than 10 test cases.
For each test case:
The first line includes two integers N and M. N is the total number of orders. M is the number of hours the shop opens.
The next N lines describe all the orders. Each line is in the following format:

month date year H R

It means that on a certain date, a customer orders R mooncakes at H o’clock. “month” is in the format of abbreviation, so it could be "Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov" or "Dec". H and R are all integers.
All the orders are sorted by the time in increasing order.
The next line contains T and S meaning that the storage life of a mooncake is T hours and the cost to store a mooncake for an hour is S.
Finally, M lines follow. Among those M lines, the ith line( i starts from 1) contains a integer indicating the cost to make a mooncake during the ith hour . The cost is no more than 10000. Jan 1st 2000 0 o'clock belongs to the 1st hour, Jan 1st 2000 1 o'clock belongs to the 2nd hour, …… and so on.

(0<N <= 2500; 0 < M,T <=100000; 0<=S <= 200; R<=10000 ; 0<=H<24)

The input ends with N = 0 and M = 0.
Output

You should output one line for each test case: the minimum cost.
Sample Input

1 10
Jan 1 2000 9 10
5 2
20
20
20
10
10
8
7
9
5
10
0 0
Sample Output

70

1个回答

devmiao
devmiao   Ds   Rxr 2017.01.22 15:06
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
HDOJ 4122 Alice's mooncake shop
用单调队列维护一个每天的最低单价。。。 Alice's mooncake shop Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2663    Accepted Submission(s): 645 Pro
hdu4122 Alice's mooncake shop(单调队列)
题目: Alice's mooncake shop Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3425    Accepted Submission(s): 868 Problem Description Th
poj 4002 Alice's mooncake shop
题目链接:http://poj.org/problem?id=4002 Alice's mooncake shop Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 525   Accepted: 162 Description The Mi
HDU 4122 Alice's mooncake shop
Alice's mooncake shop Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2795    Accepted Submission(s): 703 Problem Description The M
hdu 4122 Alice's mooncake shop(单调队列)
题目链接:hdu 4122 Alice's mooncake shop 题目大意:给定N和M,表示有N个订单,M个时刻可以做月饼,时刻以小时计算,任意时刻可以做若干个月饼。接着 N行为N个订单的信息,包括时间和数量。再给定T和S,表示每个月饼的保质时间和每保存一小时的开销。然后M行为 对应每个时刻制作月饼的代价。问说最少花费多少代价完成所有订单。 解题思路:单调队列或者RM
HDU4122 Alice's mooncake shop【单调队列】
题意:每一天做月饼的成本不一样(做的个数不限),可以放冰箱里(不过每天有费用),有保质期(相当于最多在冰箱放几天)。某个时刻有个订单,问最小费用 思路:维护一个单调不递减队列,保质期相当于区间的大小,每一天的成本和 队首的成本+放冰箱费用 作比较。还有把给个日期转化成第几天。 #include #include #include #include #include #inclu
hdu 4122 Alice's mooncake shop题解
题目大意:一个月饼店开m个小时(24小时营业),只在整点做月饼,做月饼的能力非常强。现在只需要考虑成本的问题。给m个cost值,cost[i]表示第i个小时做1个月饼的代价。   再给n个时间,从2000年1月1日0时开始计算。表示订单的截止时间。当然为了节约成本,可以提前趁成本不高的时候做月饼。但是月饼有保质期,t天,月饼放冰箱保存也需要代价,一天花费s。现在求完成n个订单最小代价。  
HDU 4122 Alice's mooncake shop
单调队列,裸的!!坑死了,说好的“All the orders are sorted by the time in increasing order. 呢,我就当成严格上升的序列了,于是就各种错。测试数据是有重复元素的!!! //#pragma comment(linker, "/STACK:1024000000,1024000000") #include #include #include
Hdu 4122 Alice's mooncake shop
题目链接 Alice's mooncake shop Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2889    Accepted Submission(s): 734 Problem Description T
HDU - 4122 Alice's mooncake shop 单调队列
The Mid-Autumn Festival, also known as the Moon Festival or Zhongqiu Festival is a popular harvest festival celebrated by Chinese people, dating back over 3,000 years to moon worship in China's Shang