【jzyz-p1326】超级教主

描述 Description

LHX教主很能跳,因为Orz他的人太多了。教主跳需要消耗能量,每跳1米就会消耗1点能量,如果教主有很多能量就能跳很高。
教主为了收集能量,来到了一个神秘的地方,这个地方凡人是进不来的。在这里,教主的正上方每100米处就有一个能量球(也就是这些能量球位于海拔100,200,300……米处),每个能量球所能提供的能量是不同的,一共有N个能量球(也就是最后一个能量球在N×100米处)。教主为了想收集能量,想跳着吃完所有的能量球。教主可以自由控制他每次跳的高度,接着他跳起把这个高度以下的能量球都吃了,他便能获得能量球内的能量,接着吃到的能量球消失。教主不会轻功,教主不会二段跳,所以教主不能因新吃到的能量而变化此次跳跃的高度。并且教主还是生活在地球上的,所以教主每次跳完都会掉下来。
问教主若要吃完所有的能量球,最多还能保留多少能量。

输入格式 Input Format

第1行包含两个正整数N,M,表示了能量球的个数和LHX教主的初始能量。
第2行包含N个非负整数,从左到右第I个数字依次从下向上描述了位于I×100米位置能量球包含的能量,整数之间用空格隔开。

输出格式 Output Format

仅包括一个非负整数,为教主吃完所有能量球后最多保留的能量。

样例输入 Sample Input

3 200
200 200 200

样例输出 Sample Output

400

数据范围

对于100%的数据,有$N<=2000000$

题解 Solution

一道DP单调性优化题,我们用f[i]表示吃到第i个能量球之后能够保留的最大能量,sum数组表示能量球的前缀和,可以得到方程:

$f[i]=max{f[j]+sum[i]−sum[j]−100∗i}(f[j]≥100∗i)$

因为$i$是与$j$无关的,所以我们可以变形为:

$f[i]=max{f[j]−sum[j]}+sum[i]−100∗i(f[j]≥100∗i)$

对于决策x和y,如果x<y,满足:$f[y]−f[x]≥sum[y]–sum[x]$那么我们只需要决策y,因为y更优

我们使用队列q储存决策的下标j,while判断队尾决策是否比i优,不优则出队,然后i入队。在取队头元素时须判断条件$f[j]≥100∗i$不满足就出队

每个元素只会出队/入队一次,所以复杂度是O(n)的。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[2000100];
int n, m;
int f[2000100];
ll sum[2000100];
int q[2000100];
int head = 0, tail = 0;

int read() {
int x = 0, y = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') y = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar();
}
return x * y;
}

void solution() {
f[0] = m;
q[++tail] = 0;
for(int i = 1; i <= n; i++) {
while (head < tail) {
if (f[q[head]] >= 100*i) break;
head++;
}
int j = q[head];
f[i] = f[j] - sum[j] + sum[i] - 100 * i;
while (f[i] - f[q[tail]] >= sum[i] - sum[q[tail]]) --tail;
q[++tail] = i;
}
printf("%d\n",f[n]);
}

int main() {
n = read();
m = read();
for(int i = 1; i <= n; i++) {
a[i] = read();
sum[i] = sum[i - 1] + a[i];
}
solution();
return 0;
}