自动搬运

查看原文

来自洛谷，原作者为

	Sol1 博客：sol1.netlify.app

搬运于2025-08-24 23:11:39，当前版本为作者最后更新于2025-03-22 20:11:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

如果序列里面的数全正或者全负，则容易看出最优方案是不进行任何划分，输出序列中的最大值与最小值的乘积即可。

否则可以转化为：选择若干个不交的区间 $[l_1,r_1], [l_2,r_2], \cdots, [l_k,r_k]$，最小化 $\sum a_{l_i} \times a_{r_i}$。

证明：记原问题的答案为 $A$，转化后的问题的答案为 $B$。对于序列的任何划分，我们可以对于划分的每一段找到序列中最小值和最大值的位置，并将这一段缩小到恰好以最小值和最大值为两个端点，这样就可以得到转化后的问题的一个方案。据此，我们有 $B \le A$。

对于转化后的问题的最优方案，显然其选择的每一个区间的两端点的正负性均相反，否则删除该区间一定更优。我们任意扩张区间，直到所有元素均被覆盖。在这个过程中，每一个区间的 $\min$ 会进一步减小（为绝对值更大的负值），$\max$ 会进一步增大（为绝对值更大的正值），从而 $\min \times \max$ 一定会进一步减小。从而我们得到了一个答案更小的原问题的方案。据此我们有 $A \le B$。综上，$A=B$。$\square$

转化后的问题容易使用 dp 解决：记 $f_i$ 表示序列以 $i$ 为结尾的前缀的最优答案，转移分类讨论 $i$ 是否被一个区间覆盖：

• $i$ 不被区间覆盖：转移为 $f_i\gets f_{i-1}$。
• $i$ 被区间覆盖：对所有 $j \leq i$，转移为 $f_i\gets f_{j-1}+a_ja_i$。

这个转移容易使用李超树优化：每次计算一个 $f_i$ 就将直线 $y=f_{i}+a_{i+1}x$ 加入李超树即可。复杂度 $O(n\log n)$。

#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;

int n;
long long a[N], f[N];

struct Line {
    long long k, b;
    Line() {}
    Line(long long k, long long b) : k(k), b(b) {}
    inline long long Eval(long long x) {return k * x + b;}
};

struct Node {
    Line l;
    Node *ls, *rs;
    Node() {}
};
Node nd[N * 2];
int top;
struct Segtree {
    Node *_root;
    //isMin = 1 => min, isMin = 0 -> max
    inline void Ins(Node *&p, long long pl, long long pr, Line nl) {
        if (!p) {
            p = &nd[++top];
            p->l = nl;
            return;
        }
        long long mid = (pl + pr) >> 1;
        if (p && nl.Eval(mid) < p->l.Eval(mid)) swap(nl, p->l);
        if (pl == pr) return;
        if (nl.k < p->l.k) Ins(p->rs, mid + 1, pr, nl);
        else Ins(p->ls, pl, mid, nl);
    }
    inline long long Query(Node *&p, long long pl, long long pr, long long x) {
        if (!p) return 3e18;
        long long mid = pl + pr >> 1;
        if (mid >= x) return min(p->l.Eval(x), Query(p->ls, pl, mid, x));
        else return min(p->l.Eval(x), Query(p->rs, mid + 1, pr, x));
    }
};
Segtree sgt;

const int L = -1e6, R = 1e6;

int main() {
    std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    bool fp = 0, fn = 0;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        if (a[i] > 0) fp = 1;
        if (a[i] < 0) fn = 1;
    }
    if (!fp || !fn) {
        long long mx = -1e9, mn = 1e9;
        for (int i = 1;i <= n;i++) {
            mx = max(mx, a[i]);
            mn = min(mn, a[i]);
        }
        cout << mx * mn << endl;
    } else {
        f[0] = 0;
        for (int i = 1;i <= n;i++) {
            f[i] = min(f[i - 1], sgt.Query(sgt._root, L, R, a[i]));
            sgt.Ins(sgt._root, L, R, Line(a[i], f[i - 1]));
        }
        cout << f[n] << endl;
    }
    return 0;
}