HDU 4122 Alice's mooncake shop （单调队列/线段树）
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4122
题意：好难读懂，读懂了也好难描述，亲们就自己凑合看看题意把
题解：开始计算每个日期到2000/1/1日0点有多少个小时，然后求出每个小时的时候每个的最小单价（包括成本+储存费用）
使用单调队列，维护队列，使之到i 生产的最优
AC代码：
#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <cstdlib>#include <cmath>#include <vector>#include <list>#include <deque>#include <queue>#include <iterator>#include <stack>#include <map>#include <set>#include <algorithm>#include <cctype>using namespace std;#define si1(a) scanf("%d",&a)#define si2(a,b) scanf("%d%d",&a,&b)#define sd1(a) scanf("%lf",&a)#define sd2(a,b) scanf("%lf%lf",&a,&b)#define ss1(s) scanf("%s",s)#define pi1(a) printf("%d\n",a)#define pi2(a,b) printf("%d %d\n",a,b)#define mset(a,b) memset(a,b,sizeof(a))#define forb(i,a,b) for(int i=a;i<b;i++)#define ford(i,a,b) for(int i=a;i<=b;i++)typedef __int64 LL;const int N=110001;const int M=1000007;const int INF=0x3f3f3f3f;const double PI=acos(-1.0);const double eps=1e-7;LL n,m,s,t;char ss[100];int mm[13],yy[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};map<string,int> mp;struct node{ int t,num;}q[3333*4],order[3333];bool isrun(int y){ if(y%400==0||(y%4==0&&y%100!=0)) return true; return false;}int run(int y1,int y2){ int num=0; for(int i=y1;i<y2;i++) if(i%400==0||(i%4==0&&i%100!=0)) num++; return num;}int main(){ mm[0]=0; for(int i=1;i<=12;i++) mm[i]=mm[i-1]+yy[i]; mp["Jan"]=1; mp["Feb"]=2; mp["Mar"]=3; mp["Apr"]=4; mp["May"]=5; mp["Jun"]=6; mp["Jul"]=7; mp["Aug"]=8; mp["Sep"]=9; mp["Oct"]=10; mp["Nov"]=11; mp["Dec"]=12; while(scanf("%I64d%I64d",&n,&m)&&(n+m)) { for(int i=0;i<n;i++) { string ss; int ri,nian,shi,ge; cin>>ss; scanf("%d%d%d%d",&ri,&nian,&shi,&order[i].num); int yue=mp[ss]; int sum=(nian-2000)*365+run(2000,nian); sum+=mm[yue-1]+ri-1; if(yue>2&&isrun(nian)) sum++; order[i].t=sum*24+shi; } int top=0,tail=0,p=0,t,s; LL sum=0; scanf("%d%d",&t,&s); for(int i=0;i<m;++i) { int a; scanf("%d",&a); while(top<tail && q[tail-1].num+(i-q[tail-1].t)*s>=a)--tail; q[tail].num=a,q[tail++].t=i; while(p<n && i == order[p].t) { while(q[top].t+t<i)++top; sum+=(q[top].num+(i-q[top].t)*s)*order[p++].num; } } printf("%I64d\n",sum); } return 0;}/*1 10Jan 1 2000 9 105 220202010108795100 0*/