#### HDU 4122 – Alice’s mooncake shop [单调队列]

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.

C++代码如下

```#include <bits/stdc++.h>
using namespace std;

struct Order{
int time, num;
};
struct Moon{
int time, spend;
};
map<string, int> dict = {
{"Jan", 1}, {"Feb", 2}, {"Mar", 3}, {"Apr", 4},
{"May", 5}, {"Jun", 6}, {"Jul", 7}, {"Aug", 8},
{"Sep", 9}, {"Oct", 10}, {"Nov", 11}, {"Dec", 12}
};
const int monthDay[2][15] = {
{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
{0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
};
list<Order> order;
list<Moon> moon;
int n, m, t, s;

bool leapYear(int y) {
return (y % 4 == 0 && y % 100) || y % 400 == 0;
}

int getTime() {
int year, day, hour; string month;
cin >> month >> day >> year >> hour;
int res = 0;
for(int i = 2000; i < year; ++i)
res += leapYear(i) ? 366 * 24 : 365 * 24;
for(int i = 1; i < dict[month]; ++i)
res += monthDay[leapYear(year)][i] * 24;
res += (day - 1) * 24;
res += hour;
return res;
}

int main() {
ios::sync_with_stdio(false);
while(cin >> n >> m, n || m) {
order.clear(); moon.clear();
for (int i = 0; i < n; ++i) {
Order cur; cur.time = getTime();
cin >> cur.num;
order.push_back(cur);
}
cin >> t >> s;
long long res = 0;
for(int i = 0; i < m; ++i) {
int cost; cin >> cost;
while(!moon.empty() && moon.back().spend + s * (i - moon.back().time) >= cost)
moon.pop_back();
moon.push_back(Moon{i, cost});
while(!order.empty() && i == order.front().time) {
while(!moon.empty() && i - moon.front().time > t)
moon.pop_front();
res += order.front().num * (moon.front().spend + s * (i - moon.front().time));
order.pop_front();
}
}
cout << res << endl;
}
return 0;
}
```