题解：P11958 「ZHQOI R1」划分

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

否则可以转化为：选择若干个不交的区间

[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)

。

CPP

#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;
}

题解：P11958 「ZHQOI R1」划分

文章操作

相关推荐

评论

题解：P11958 「ZHQOI R1」划分