题目大意：
一个月饼店开m个小时（24小时营业），只在整点做月饼，做月饼的能力非常强。现在只需要考虑成本的问题。给m个cost值，cost[i]表示第i个小时做1个月饼的代价。
再给n个时间，从2000年1月1日0时开始计算。表示订单的截止时间。当然为了节约成本，可以提前趁成本不高的时候做月饼。但是月饼有保质期，t天，月饼放冰箱保存也需要代价，一天花费s。
现在求完成n个订单最小代价。
分析：
对于第i个订单，首先计算出是第ti个营业时间。这里考虑每个月饼的单价。所以第i个订单的月饼只能在[ti - t,ti]做。考虑时间j有个订单，假设时间i完成代价是最小的。那么第j个订单的代价就是cost[i] + (j - i) * s。我们用单调队列去维护下这个区间就可以了
#include <algorithm> #include <string> #include <string.h> #include <vector> #include <map> #include <stack> #include <set> #include <queue> #include <math.h> #include <cstdio> #include <iomanip> #include <time.h> #include <bitset> #include <cmath> #include <sstream> #include <iostream> #define LL long long #define INF 0x3f3f3f3f #define ls nod<<1 #define rs (nod<<1)+1 const double eps = 1e-10; const int maxn = 1e5 + 10;; const LL mod = 1e9 + 7; int sgn(double a){return a < -eps ? -1 : a < eps ? 0 : 1;} using namespace std; struct node { LL val,idx; }; LL cost[maxn],ti[maxn]; LL m,n,h,r,s,t; int days[2][13] = {{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} }; int getmon(char ss[]) { if(strcmp(ss,"Jan") == 0) return 1; else if(strcmp(ss,"Feb") == 0) return 2; else if(strcmp(ss,"Mar") == 0) return 3; else if(strcmp(ss,"Apr") == 0) return 4; else if(strcmp(ss,"May") == 0) return 5; else if(strcmp(ss,"Jun") == 0) return 6; else if(strcmp(ss,"Jul") == 0) return 7; else if(strcmp(ss,"Aug") == 0) return 8; else if(strcmp(ss,"Sep") == 0) return 9; else if(strcmp(ss,"Oct") == 0) return 10; else if(strcmp(ss,"Nov") == 0) return 11; else if(strcmp(ss,"Dec") == 0) return 12; else return -1; } LL getid(int y,int m,int d,int h) { int loop = (y % 4 == 0 && y % 100 != 0) || y % 400 == 0; LL ret = d - 1; for(int i = 1;i < m;i ++) ret += days[loop][i]; for(int i = 2000;i < y;i ++) { if((i % 4 == 0 && i % 100 != 0) || i % 400 == 0) ret += 366; else ret += 365; } ret *= 24; ret += h; return ret + 1; } char mo[34]; int da,ye; LL rr[maxn]; int main() { while (~scanf("%lld%lld",&n,&m)) { if (n == 0 && m == 0) break; for(int i = 1;i <= n;i ++) { scanf("%s",mo); scanf("%d%d%lld%lld",&da,&ye,&h,&r); ti[i] = getid(ye,getmon(mo),da,h); rr[i] = r; } scanf("%lld%lld",&t,&s); for (int i = 1;i <= m;i++) { scanf("%lld",&cost[i]); } LL ans = 0; deque<node> q; for (int i = 1,j = 1;i <= m && j <= n;i++) { while (!q.empty() && q.back().val+(i-q.back().idx)*s >= cost[i]) q.pop_back(); node nd; nd.val = cost[i],nd.idx = i; q.push_back(nd); while (!q.empty() && q.front().idx < i-t) q.pop_front(); while (ti[j] == i) { ans += rr[j]*(q.front().val + (i-q.front().idx)*s); j++; } } printf("%lld ",ans); } return 0; }