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*/