再给n个时间，从2000年1月1日0时开始计算。表示订单的截止时间。当然为了节约成本，可以提前趁成本不高的时候做月饼。但是月饼有保质期，t天，月饼放冰箱保存也需要代价，一天花费s。现在求完成n个订单最小代价。
题目分析：对于第i个订单，首先计算出是第ti个营业时间。这里考虑每个月饼的单价。所以第i个订单的月饼只能在(ti - t,ti]做。考虑时间j有个订单，假设时间i完成代价是最小的。那么第j个订单的代价就是cost[i] + (j - i) * s，整理一下：cost[i] - i*s + j*s，这里我们只需要维护cost[i] - i*s即可。即维护(订单时间-t，订单时间]这个区间里的cost[i] - i*s的最小值即可。所以可以用单调队列或者线段树来维护。
详情请见代码：（2份代码写一起了）
#include#include #include #include using namespace std; const int N = 2505; const int M = 100005; const int inf = 0x3f3f3f3f; typedef __int64 ll; ll que[M]; int head,tail; ll cost[M],ti[N]; ll tree[M<<2]; 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 i; 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(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[M]; void build(int num,int s,int e) { tree[num] = inf; if(s == e) return; int mid = (s + e)> >1; build(num<<1,s,mid); build(num<<1|1,mid + 1,e); } void insert(int num,int s,int e,int pos,ll val) { if(s == e) { tree[num] = val; return; } int mid = (s + e)>>1; if(pos > mid) insert(num<<1|1,mid + 1,e,pos,val); else insert(num<<1,s,mid,pos,val); tree[num] = min(tree[num<<1],tree[num<<1|1]); } ll query(int num,int s,int e,int l,int r) { if(s == l && e == r) return tree[num]; int mid = (s + e)>>1; if(r <= mid) return query(num<<1,s,mid,l,r); else { if(l > mid) return query(num<<1|1,mid + 1,e,l,r); else return min(query(num<<1,s,mid,l,mid),query(num<<1|1,mid + 1,e,mid + 1,r)); } } int main() { ll ans; int i,j; while(scanf("%I64d%I64d",&n,&m),(m + n)) { for(i = 1;i <= n;i ++) { scanf("%s",mo); scanf("%d%d%I64d%I64d",&da,&ye,&h,&r); ti[i] = getid(ye,getmon(mo),da,h); rr[i] = r; } scanf("%I64d%I64d",&t,&s); build(1,1,m); for(i = 1;i <= m;i ++) { scanf("%I64d",&cost[i]); cost[i] -= s*i; insert(1,1,m,i,cost[i]); } ans = 0; for(i = 1;i <= n;i ++) { if(ti[i] > m) break; if(ti[i] - t + 1 < 1) ans += rr[i] * (query(1,1,m,1,ti[i]) + ti[i] * s); else ans += rr[i] * (query(1,1,m,ti[i] - t + 1,ti[i]) + ti[i] * s); } // head = tail = 0;单调队列部分 // i = 1; // j = 1; // for(;i <= m && j <= n;i ++) // { // while(head < tail && cost[que[tail - 1]] >= cost[i]) // tail --; // que[tail ++] = i; // if(head < tail && que[head] < i - t) // head ++; // while(ti[j] == i)注意这里可能某个时间有多个订单，所以要while！！Orz ns // { // ans += rr[j] * (cost[que[head]] + i * s); // j ++; // } // } printf("%I64d\n",ans); } return 0; } /* 1 10 Jan 1 2000 9 10 5 2 20 20 20 10 10 8 7 9 5 10 0 0 */