hdu4122

题目很长，有点恶心，但实际上是个单调队列

没搞出来，题解 https://blog.csdn.net/lvshubao1314/article/details/46910271

#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll times[],num[],cost[],q[];//订单时间，订单数量，每个时间做蛋糕的代价，单调队列

ll n,m,T,S;//n个订单，m个做蛋糕时间(连续的)，蛋糕寿命，每小时保存代价

map<string,int>mp;

int sum[];

void init(){

    mp["Jan"]=,mp["Feb"]=,mp["Mar"]=;

    mp["Apr"]=,mp["Mar"]=,mp["Jun"]=;

    mp["Jul"]=,mp["Aug"]=,mp["Sep"]=;

    mp["Oct"]=,mp["Nov"]=,mp["Dec"]=;

    sum[]=,sum[]=,sum[]=sum[]+,sum[]=sum[]+,sum[]=sum[]+,sum[]=sum[]+,sum[]=sum[]+;

    sum[]=sum[]+,sum[]=sum[]+,sum[]=sum[]+,sum[]=sum[]+,sum[]=sum[]+;

}

int get(int y,int m,int d,int t)

{

    int ans=;

    for(int i=; i<y; i++)

    {

        if((i%==&&i%!=)||i%==)

            ans+=;

        else

            ans+=;

    }

    if((y%==&&y%!=)||y%==)

    {

        ans+=sum[m-];

        if(m->=)ans++;

    }

    else

    {

        ans+=sum[m-];

    }

    ans+=(d-);

    return ans*+t;

}

int main(){

    init();

    while(scanf("%lld%lld",&n,&m),n){

        for(int i=;i<n;i++){

            int year,day,t;

            char mon[];

            scanf("%s%d%d%d%lld",mon,&day,&year,&t,&num[i]);

            times[i]=get(year,mp[mon],day,t);

        }

        scanf("%lld%lld",&T,&S);

        int tail=,head=,k=;

        ll cnt=;

        for(int i=;i<m;i++){

            scanf("%lld",&cost[i]);

            while(head<tail && cost[q[tail-]]+S*(i-q[tail-])>=cost[i])tail--;//单调队列不是按照cost排序，而是按照制作成本+保存成本从小到大排序

            q[tail++]=i;

            while(i==times[k]){

                while(head<tail- && i-q[head]>T) head++;

                cnt+=num[k]*(cost[q[head]]+S*(i-q[head]));

                k++;

            }

        }

        printf("%lld\n",cnt);

    }

}