hdu 3738 The Sweat Shop単調スタックと貪欲な思想

The Sweat Shop
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 90    Accepted Submission(s): 28
Problem Description
Many people spend thier lives in sweat shop in China. The boss of one of the famous sweat shop, GXX, is considering about the employment plan of her company.
He already knows that in the next N days, how many worker are needed for this day's work, a[i]. In additional, he will spend x yuan on recruit a worker, y yuan on fire a worker. If a worker spend a day on work in his company, GXX must pay z yuan for the wages per day.
GXX has no work before the first day and he decide to fire all the workers after these N days. Now comes to the question, how much he will pay on the employment plan in minimum.
 
Input
The first line contains only one integer T, denoting the number of test cases.
For each test cases, the first line contains only one integer N, denoting the number of days. (1 <= N <= 100000)
The next line contains three integers, x, y and z, denoting the amount of spend on recruit, fire a worker, and the daily salary of a worker. (1 <= x,y,z <= 100000)
The third line contains N integers, a[i], denoting the minimum number of workers needed for the i-th day. (1 <= a[i] <= 100000)
 
Output
For each test cases, output a single number denoting the minimum amount GXX should spend on employment plan.
 
Sample Input

   
   
   
   

    
    
    
    1
3
10 10 1
2 1 2
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    46
   
   
   
   

 
问题:n日の仕事をするためにいくつかの労働者が必要で、毎日必要な労働者の数を教えて、1人の労働者を募集するにはx元が必要で、1人の労働者を除名するにはy元が必要で、労働者の毎日の给料はz元で、n日の仕事が终わった后、すべての労働者を除名する必要があります.
考え方:単調でスタックに保存されているのはi-1日を満たす可能性のある人数であり、最適化に相当する.i日目は、スタックの中でa[i]より小さいものと、a[i]より大きいものを遍歴するだけでよく、より多くの人を雇う必要はありません.

#include <iostream>
#include <stdio.h>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
typedef __int64 ll;

using namespace std;

ll a[100009];
ll q[100009];
ll dp[100009];

int main()
{
    int T,n;
    ll x,y,z;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        scanf("%I64d%I64d%I64d",&x,&y,&z);

        for(int i=1;i<=n;i++)
            scanf("%I64d",&a[i]);

        int t=0;
        q[t]=0;
        a[0]=0;
        dp[0]=0;

        for(int i=1;i<=n;i++)
        {
            dp[i]=1ll<<60;
            while(t>=0 && a[i]>a[q[t]])
            {
                ll tmp=dp[q[t]]+a[q[t]]*z*(i-q[t]);
                tmp+=(a[i]-a[q[t]])*(x+z);
                dp[i]=min(dp[i],tmp);
                t--;
            }

            if(t>=0)//            
            {
                ll tmp=dp[q[t]]+(a[q[t]]-a[i])*y+a[i]*(i-q[t])*z;
                dp[i]=min(dp[i],tmp);
            }
            q[++t]=i;
        }

        dp[n]+=a[n]*y;

        printf("%I64d
",dp[n]);
    }

    return 0;
}