Codeforces 855B(枚举)

Codeforces 855B
题意:给一个数组,求$p \cdot a_i + q \cdot a_j + r \cdot a_k$的最大值$(1 \leq i \leq j \leq k \leq n) $
维护前缀后缀最大值/最小值,然后我们枚举中间值$j$,算每个$j$作为中间点的值
然后$q$的贡献为$q \cdot a_i$
而对于$p$, 如果有$p \geq 0$,那么$p$的贡献为$p \cdot lmax_i$,反之$p$的贡献为$p \cdot lmin_i$
对于$r$, 如果有$r \geq 0$,那么$r$的贡献为$r \cdot rmax_i$,反之$r$的贡献为$r \cdot rmin_i$
然后最后可以得出一个最大的值,即为答案

Codeforces Submission

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
const LL INF = 9223372036854775807;
LL n, p, q, r, a[MAXN], lmax[MAXN], lmin[MAXN], rmax[MAXN], rmin[MAXN];
void clean() {
for (LL i = 0; i <= n + 1; i++) lmax[i] = rmax[i] = -INF, lmin[i] = rmin[i] = INF;
}
void solve() {
clean();
for (LL i = 1; i <= n; i++) scanf("%I64d", &a[i]);
for (LL i = 1; i <= n; i++) lmax[i] = max(lmax[i - 1], a[i]), lmin[i] = min(lmin[i - 1], a[i]);
for (LL i = n; i >= 1; i--) rmax[i] = max(rmax[i + 1], a[i]), rmin[i] = min(rmin[i + 1], a[i]);
LL ans = -INF;
for (LL i = 1; i <= n; i++) {
LL tot = q * a[i];
if (p < 0) tot += p * lmin[i]; else tot += p * lmax[i];
if (r < 0) tot += r * rmin[i]; else tot += r * rmax[i];
ans = max(ans, tot);
}
printf("%I64d\n", ans);
}
int main() {
scanf("%I64d%I64d%I64d%I64d", &n, &p, &q, &r), solve();
return 0;
}

------ 本文结束 ------