【CF573E】Bear and Bowling

题面

洛谷

题解

首先有一个贪心的结论：

我们一次加入每个数，对于\(\forall i\)，位置\(i\)的贡献为\(V_i = k_i\times a_i+b_i\)，其中\(k_i\)为位置\(i\)之前被选的数的个数，\(b_i\)为\(i\)之后被选的数的和。
那么我们每次选这个贡献最大的位置一定最优。

然后来证一下这个结论的正确性（直接蒯了\(\text {i} \color{#FF0000} {\text {tst}}\)的）：

引理：在上述贪心策略下，如果\(a_i>a_j\)且\(i<j\)，则选\(i\)之前不可能选\(j\)。

证明考虑归纳：\(i,j\)中间不存在被选中的元素时是平凡的，如果\(i,j\)中间存在p个选中的元素，若\(V_i<V_j\)则一定在\([i,j]\)之间存在至少一个\(x\)满足\(a_x<a_j\)，此时没有选\(i\)所以不可能选择\(x\)，与假设不符，QED。

接下来假设贪心策略不正确，即在选择了集合\(A\)之后将下标为\(x\)的位置选中，但是最优的答案是选择集合\(A+B\)，其中\(x\notin B\)。那么考虑：

1、如果\(B\)中存在位置在\(x\)左边，考虑在\(x\)左边的最右位置\(y\)，那么此时有\(a_y\leq a_x,V_x≥V_y\)。此时加入集合\(B\)中的其他元素考虑\(V_x,V_y\)的变化，那么在\(x\)右边的元素对\(V_x,V_y\)的贡献一样，在\(y\)左边的元素对\(V_x,V_y\)的贡献是\(a_x,a_y\)，而\(x,y\)中间没有在\(B\)中的元素，所以可以发现在其他元素加入之后\(V_x\geq V_y\)，所以将\(B\)中\(y\)换成\(x\)结果不劣。

2、如果\(B\)中只有在\(x\)右边的元素，考虑在\(x\)右边的最左位置\(y\)，那么\(B\)集合其他的元素对\(V_x,V_y\)的贡献是一样的，所以把\(y\)换成\(x\)也不会更劣。

故上述假设不成立，贪心正确性证毕。

考虑分块维护这个最大值。
每次选完最大值，就相当于对于选定的\(pos\)，\(pos\)前的位置\(i\)中\(b_i\)均加上\(a_{pos}\)，\(pos\)后的位置\(i\)中\(k_i\)均加上一。因为对于同一块我们加上的\(k,b\)是一样的，而\(pos\)所在的块可以\(\sqrt n\)暴力重构，所以我们分块维护凸壳就可以了。

代码

#include <iostream> 
#include <cstdio> 
#include <cstdlib> 
#include <cstring> 
#include <cmath> 
#include <algorithm>
#include <queue> 
using namespace std; 

const int MAX_N = 1e5 + 5; 
const int LEN = 320; 
int N, a[MAX_N], id[MAX_N], bel[MAX_N], L[LEN], R[LEN]; 
long long tk[LEN], tb[LEN], f[MAX_N], ans; 
double slope(int i, int j) { 
    if (a[i] == a[j]) return f[i] > f[j] ? -1e20 : 1e20; 
    else return (double)(f[i] - f[j]) / (a[i] - a[j]); 
} 
long long calc(int i) { return f[i] + tk[bel[i]] * a[i] + tb[bel[i]]; } 
struct Hull { 
    deque<int> q; 
    void clear() { q.clear(); } 
    void insert(int i) { 
        while (q.size() > 1 && slope(q[q.size() - 2], q[q.size() - 1]) 
                             < slope(q[q.size() - 1], i)) q.pop_back(); 
        q.push_back(i); 
    } 
    pair<long long, int> query() { 
        while (q.size() > 1 && calc(q[0]) <= calc(q[1])) 
            q.pop_front(); 
        return make_pair(calc(q[0]), q[0]); 
    } 
} S[LEN]; 
void modify(int l, int ed, int k, int b) { 
    while (l <= ed) { 
        int x = bel[l], r = min(R[x], ed); 
        if (l == L[x] && r == R[x]) tk[x] += k, tb[x] += b; 
        else for (int i = l; i <= r; i++) f[i] += 1ll * k * a[i] + b; 
        l = r + 1; 
    } 
} 
pair<long long, int> query(int l, int ed) { 
    pair<long long, int> res = make_pair(0, 0); 
    while (l <= ed) { 
        int x = bel[l], r = min(R[x], ed); 
        if (l == L[x] && r == R[x]) res = max(res, S[x].query()); 
        else for (int i = l; i <= r; i++) res = max(res, make_pair(calc(i), i)); 
        l = r + 1; 
    } 
    return res; 
} 
void build(int x) { 
    for (int i = L[x]; i <= R[x]; i++) f[i] += tk[x] * a[i] + tb[x]; 
    tk[x] = tb[x] = 0, S[x].clear(); 
    for (int i = L[x]; i <= R[x]; i++) S[x].insert(id[i]); 
} 
int main () { 
#ifndef ONLINE_JUDGE 
    freopen("cpp.in", "r", stdin); 
#endif 
    scanf("%d", &N); 
    for (int i = 1; i <= N; i++) { 
        scanf("%d", a + i); 
        f[i] = a[i], id[i] = i; 
        bel[i] = (i - 1) / LEN + 1; 
        if (!L[bel[i]]) L[bel[i]] = i; 
        R[bel[i]] = i; 
    } 
    for (int i = 1; i <= bel[N]; i++) 
        sort(&id[L[i]], &id[R[i] + 1], [](int l, int r) { return a[l] < a[r]; }), build(i); 
    long long ans = 0; 
    while (1) { 
        pair<long long, int> res = query(1, N); 
        if (res.first <= 0) break; 
        ans += res.first; 
        f[res.second] = -1ll << 60; 
        if (res.second > 1) modify(1, res.second - 1, 0, a[res.second]); 
        if (res.second < N) modify(res.second + 1, N, 1, 0); 
        build(bel[res.second]); 
    } 
    printf("%lld\n", ans); 
    return 0; 
} 

【CF573E】Bear and Bowling

原文：https://www.cnblogs.com/heyujun/p/11766283.html