Description
给定三个数 (p~,~q~,~r~),以及一个数组 (a)，
找出三个数 (i~,~j~,~k) ，其中 (i~leq~j~leq~k) 最大化 (p~ imes~a_i~+~q~ imes~a_j~+~r~ imes~a_r)
Input
第一行是数组长度 (n) 以及 (p~,~q~,~r~)。
第二行 (n) 个数代表这个数组
Output
输出一个整数代表答案
Hint
(-10^5~leq~n~leq~10^5)
其他数据 (in~[-10^9~,~10^9])
Solution
考虑最暴力的方法，枚举 (i~,~j~,~k) ，计算答案，时间复杂度(O(n^3))
然后考虑如果枚举了其中两个值，剩下一个可以直接通过查询区间最值确定。例如，如果枚举了 (i~,~j)，则 (k) 对应的最优解一定是 ( (k~>~0) 时) (k~ imes~max_{s~=~j}^{n}~a_s)，（ (k~leq~0) 时） (k~ imes~min_{s~=~j}^{n}~a_s)。枚举其它两个元素同理。这样就可以用ST预处理区间最值，然后做到 (O(1)) 查询，复杂度 (O(nlog n)-O(n^2)) 。
考虑上述做法的缺陷在于枚举量还是太大，能否可以只枚举一个位置呢？我们发现如果枚举一个位置以后可以确定剩下两个区间，就可以只枚举一个位置。于是发现枚举 (j) 符合要求。于是只枚举 (j) 按照上面的方法求 (i~,~k) 的对应答案。时间复杂度 (O(nlog n)~-~O(n))
Code
#include <cmath>
#include <cstdio>
#include <algorithm>
#ifdef ONLINE_JUDGE
#define freopen(a, b, c)
#endif
#define rg register
#define ci const int
#define cl const long long
typedef long long int ll;
namespace IPT {
const int L = 1000000;
char buf[L], *front=buf, *end=buf;
char GetChar() {
if (front == end) {
end = buf + fread(front = buf, 1, L, stdin);
if (front == end) return -1;
}
return *(front++);
}
}
template <typename T>
inline void qr(T &x) {
rg char ch = IPT::GetChar(), lst = ' ';
while ((ch > '9') || (ch < '0')) lst = ch, ch=IPT::GetChar();
while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = IPT::GetChar();
if (lst == '-') x = -x;
}
template <typename T>
inline void ReadDb(T &x) {
rg char ch = IPT::GetChar(), lst = ' ';
while ((ch > '9') || (ch < '0')) lst = ch, ch = IPT::GetChar();
while ((ch >= '0') && (ch <= '9')) x = x * 10 + (ch ^ 48), ch = IPT::GetChar();
if (ch == '.') {
ch = IPT::GetChar();
double base = 1;
while ((ch >= '0') && (ch <= '9')) x += (ch ^ 48) * ((base *= 0.1)), ch = IPT::GetChar();
}
if (lst == '-') x = -x;
}
namespace OPT {
char buf[120];
}
template <typename T>
inline void qw(T x, const char aft, const bool pt) {
if (x < 0) {x = -x, putchar('-');}
rg int top=0;
do {OPT::buf[++top] = x % 10 + '0';} while (x /= 10);
while (top) putchar(OPT::buf[top--]);
if (pt) putchar(aft);
}
const int maxn = 100010;
const ll INF = -1000000000ll;
int n;
int LOG[maxn];
ll p, q, r, ans = -3000000000000000010ll;
ll MU[maxn], ST[2][20][maxn];
ll ask(ci, ci, ci);
int main() {
freopen("1.in", "r", stdin);
qr(n); qr(p); qr(q); qr(r);
for (rg int i = 1; i <= n; ++i) qr(MU[i]);
for (rg int i = 0; (1 << i) <= n; ++i) {
LOG[1 << i] = i;
}
for (rg int i = 3; i <= n; ++i) if(!LOG[i]) LOG[i] = LOG[i - 1];
for (rg int i = 0; i < 20; ++i)
for (rg int j = 0; j < maxn; ++j)
ST[1][i][j] = INF;
for (rg int i = 0; i < 20; ++i)
for (rg int j = 0; j < maxn; ++j)
ST[0][i][j] = -INF;
for (rg int i = 1; i <= n; ++i) ST[1][0][i] = ST[0][0][i] = MU[i];
for (rg int i = 1; i < 20; ++i) {
int len = (1 << i) - 1;
for (rg int l = 1; l <= n; ++l) {
int r = l + len; if (r > n) break;
ST[0][i][l] = std::max(ST[0][i - 1][l], ST[0][i - 1][l + (1 << (i - 1))]);
ST[1][i][l] = std::min(ST[1][i - 1][l], ST[1][i - 1][l + (1 << (i - 1))]);
}
}
for (rg int i = 1; i <= n; ++i) {
ans = std::max(q * MU[i] + p * ask(1, i, p < 0) + r * ask(i, n, r < 0), ans);
}
qw(ans, '
', true);
return 0;
}
ll ask(ci l, ci r, ci cur) {
int len = r - l + 1;
if (cur) return std::min(ST[1][LOG[len]][l], ST[1][LOG[len]][r - (1 << LOG[len]) + 1]);
else return std::max(ST[0][LOG[len]][l], ST[0][LOG[len]][r - (1 << LOG[len]) + 1]);
}
Summary
这次貌似也没啥好summary的……就是我好菜啊ST都调了半天