題意：
? ? ? 有一個加工廠加工月餅的，這個工廠一共開業m小時，2000年1月1日0點是開業的第一個小時，每個小時加工月餅的價錢也不一樣，然后每個月餅的保質期都是t天，因為要放在冰箱里保存，所以在保質期期間每天每個月餅的花費是s，他接到了n個訂單，問你完成這n個訂單的最小花費是多少？


思路：
? ? ?想到這樣一個性質，在一個序列里面某一個位置的值是由他前面的某一個范圍中的一個得到的，而且我們要當前這個位置最小（或者最大），這樣的問題可以用單調隊列解決，這個題目我們可以弄一個遞增的單調隊列，小的那頭要保證不過期，大的那頭要保證遞增，這樣就ok了，還有對于這個題目，我的方法是吧所有的訂單日期全都處理成小時（就是于題目中的m對應）去做，這樣能清晰點，還有就是有兩個小提示，訂單當天做也來得及，還有一個就是兩個訂單的日期可能相同，別的沒什么了，具體細節看下面代碼。
? ? ??


#include<map>
#include<string>
#include<stdio.h>
#include<string.h>


#define N 2500 + 50


using namespace std;


map<__int64 ,__int64>mark;
map<string ,int>mk;
__int64 ry[13] = {0 ,31 ,29 ,31 ,30 ,31 ,30 ,31 ,31 ,30 ,31 ,30 ,31};
__int64 py[13] = {0 ,31 ,28 ,31 ,30 ,31 ,30 ,31 ,31 ,30 ,31 ,30 ,31};
__int64 C[110000] ,node[N];
__int64 hash[110000];
int Q[110000];
__int64 tou ,wei;


void DB()
{
? ?mk["Jan"] = 1; mk["Feb"] = 2; mk["Mar"] = 3;
? ?mk["Apr"] = 4; mk["May"] = 5; mk["Jun"] = 6;
? ?mk["Jul"] = 7; mk["Aug"] = 8; mk["Sep"] = 9;
? ?mk["Oct"] = 10; mk["Nov"] = 11; mk["Dec"] = 12;
}


bool jude(__int64 now)
{
? ?return now % 400 == 0 || now % 4 == 0 && now % 100 != 0;
}


void insert(int t ,__int64 tt,__int64 cost)
{
? ?for(int i = wei ;i > tou ;i --)
? ?{
? ? ? if(C[t] <= (__int64)(t - Q[wei]) * cost + C[Q[wei]])
? ? ? wei --;
? ? ? else break;
? ?}
? ?Q[++wei] = t;
? ?for(int i = tou + 1;i <= wei ;i ++)
? ?if(t - Q[i] > tt) tou ++;
}
? ?


int main ()
{
? ?int n ,m ,a ,i;
? ?__int64 y ,r ,h ,t ,cost;
? ?char mouse[10];
? ?DB();
? ?while(~scanf("%d %d" ,&n ,&m) && n + m)
? ?{
? ? ? mark.clear();
? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? {
? ? ? ? ?scanf("%s %I64d %I64d %I64d %I64d" ,mouse ,&r ,&y ,&h ,&node[i]);
? ? ? ? ?__int64 now = mk[mouse] * 10000 + y * 1000000 + r * 100 + h * 1; ? ? ?
? ? ? ? ?if(mark[now]) node[mark[now]] += node[i];
? ? ? ? ?else mark[now] = i; ??
? ? ? }
? ? ? memset(hash ,0 ,sizeof(hash));
? ? ? __int64 nn = 2000,yy = 1 ,rr = 1,ss = 0;
? ? ? if(mark[nn*1000000+yy*10000+rr*100+ss*1])
? ? ? {
? ? ? ? ?hash[1] = mark[nn*1000000+yy*10000+rr*100+ss*1];
? ? ? }
? ? ? for(i = 2 ;i <= m ;i ++)
? ? ? {
? ? ? ? ?ss ++;
? ? ? ? ?if(ss == 24) {ss = 0 ,rr ++;}
? ? ? ? ?if(jude(nn) && rr == ry[yy] + 1 || !jude(nn) && rr == py[yy] + 1)
? ? ? ? ?{yy ++ ,rr = 1;}
? ? ? ? ?if(yy == 13) {yy = 1 ;nn ++;}
? ? ? ? ?if(mark[nn*1000000+yy*10000+rr*100+ss*1])
? ? ? ? ?hash[i] = mark[nn*1000000+yy*10000+rr*100+ss*1];?
? ? ? }
? ? ? scanf("%I64d %I64d" ,&t ,&cost);?
? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? scanf("%I64d" ,&C[i]);
? ? ? tou = wei = 0;
? ? ? __int64 Ans = 0;
? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? { ? ?
? ? ? ? ?insert(i ,t ,cost);
? ? ? ? ?if(hash[i])
? ? ? ? ?{ ?
? ? ? ? ? ? int T = Q[tou + 1];
? ? ? ? ? ? Ans += ?C[T] * node[hash[i]] + node[hash[i]] * (__int64)(i - T) * cost;
? ? ? ? ?} ??
? ? ? }
? ? ? printf("%I64d\n" ,Ans); ? ? ?
? ? ??
? ?}
? ?return 0;
}
? ? ??
? ? ? ? ?
? ? ? ? ?
? ? ? ? ?
? ? ? ? ?
? ? ??
? ?
? ?
? ?
? ?

總結

以上是生活随笔為你收集整理的hdu4122 制作月饼完成订单的最小花费的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。