2015
02-22

# The Sweat Shop

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.

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)

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)

1
3
10 10 1
2 1 2

46

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define N 100010
int n;
__int64  a[N], x, y, z;
int q[N], ed;
__int64 min(__int64 a,__int64 b )
{
return a<b?a:b;
}
void solve() {
__int64 res = a[0] * x + a[n - 1] * y;
for (int i = 0; i < n; ++i) {
res += a[i] * z;
if(i) {
if (a[i - 1] > a[i])
res += (a[i - 1] - a[i]) * y;
else
res += (a[i] - a[i - 1]) * x;
}
}
ed = 0;
q[ed++] = 0;
for (int i = 1; i < n; ++i) {
if (a[q[ed - 1]] >= a[i]) q[ed++] = i;
else {
while (ed > 1 && a[q[ed - 1]] < a[i]) {
--ed;
/* t是解雇工人的数目 ，
tmp---是留着这个工人省钱还是解雇这个工人省的钱 ？？
*/
__int64 tmp, t = min(a[i], a[q[ed - 1]]) - a[q[ed]];

if ((tmp = (x + y - (i - q[ed - 1] - 1) * z) * t) > 0) {

res -= tmp;
//printf("\n........\nq[ed]=%d l=%d r=%d tmp=%d\n",q[ed],q[ed - 1],i,tmp);
}
}
if (a[q[ed - 1]] <= a[i]) --ed;
q[ed++] = i;

}
}
printf("%I64d\n", res);
}
int main() {
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
int cas;
scanf("%d", &cas);
while (cas--) {
scanf("%d", &n);
scanf("%I64d%I64d%I64d", &x, &y, &z);
for (int i = 0; i < n; ++i) {
scanf("%I64d", &a[i]);
}
solve();
}
return 0;
}

1. 我没看懂题目
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
第二个是7 0 6 -1 1 -6 7输出是14 7 7
不知道题目例子是怎么得出来的