题解 CF631E 【Product Sum】

2019-04-17 20:34:58


${\large \color{#ff7daf}{\text{CF631E Product Sum}}}$

题意:整个序列的分数为 $\sum\limits_{i=1}^{n}a_i·i$ ,你可以将某个元素向任意方向移动任意位,求一次该操作后可获得的最大分数。

设 $sum_i = \sum\limits_{j=1}^{i}a_i$

接下来以将第 $i$ 个元素向前移动第 $j$ 个位置为例:

将 $a_i$ 移到 $j$ 增加的分数: $(j-i)·a_i-(sum_j-sum_i)$

尝试斜率优化,设 $k > j$ 且选择 $k$ 要优于选择 $j$:

$(j-i)·a_i-(sum_j-sum_i)<(k-i)·a_i-(sum_k-sum_i)$

移项后合并同类项:

$j·a_i-sum_j<k·a_i-sum_k$

再移项:

$sum_k-sum_j<(k-j)·a_i$

$\frac{sum_j-sum_k}{j-k}<a_i$

维护上凸壳,二分进行决策即可。

将某一元素向后移动类似,此处不做赘述。

代码(不可AC,但是正确(^_^)):


#include <cstdio>
#include <cstring>
#include <algorithm>

#define maxn 200005
#define K(x, y) ((1.0 * w[x] - w[y]) / (1.0 * (x) - (y)))
#define Calc1(x, y) (sum[(x) - 1] - sum[(y) - 1] - a[x] * ((x) - (y)))
#define Calc2(x, y) (a[x] * ((y) - (x)) - (sum[(y)] - sum[(x)]))

using namespace std;
typedef int LL;

int n, stk[maxn], top = 0;
LL a[maxn], sum[maxn], ans = 0, w[maxn], res = 0;

inline int read()
{
    char ch = getchar();
    int ret = 0, f = 1;
    while (ch > '9' || ch < '0')
    {
        if (ch == '-')
            f = -f;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        ret = ret * 10 + ch - '0', ch = getchar();
    return ret * f;
}

int main()
{
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    n = read();
    for (int i = 1; i <= n; ++i)
    {
        a[i] = read();
        sum[i] = sum[i - 1] + a[i];
        ans += 1ll * i * a[i];
    }
    stk[1] = 1, stk[2] = 2, top = 2;
    w[1] = sum[0], w[2] = sum[1];
    res = max(0ll, Calc1(2, 1));
    for (int i = 3; i <= n; ++i)
    {
        int l = 1, r = top - 1, j = stk[top];
        while (l <= r)
        {
            int mid = (r - l >> 1) + l;
            if (K(stk[mid + 1], stk[mid]) > a[i])
                r = mid - 1, j = stk[mid];
            else
                l = mid + 1;
        }
        res = max(res, Calc1(i, j));
        w[i] = sum[i - 1];
        while (top > 1)
        {
            if (K(i, stk[top]) > K(stk[top], stk[top - 1]))
                break;
            --top;
        }
        stk[++top] = i;
    }
    stk[1] = n, stk[2] = n - 1, top = 2;
    w[n] = sum[n], w[n - 1] = sum[n - 1];
    res = max(res, Calc2(n - 1, n));
    for (int i = n - 3; i > 0; --i)
    {
        int l = 1, r = top - 1, j = stk[top];
        while (l <= r)
        {
            int mid = (r - l >> 1) + l;
            if (K(stk[mid + 1], stk[mid]) < a[i])
                r = mid - 1, j = stk[mid];
            else
                l = mid + 1;
        }
        res = max(res, Calc2(i, j));
        w[i] = sum[i];
        while (top > 1)
        {
            if (K(i, stk[top]) < K(stk[top], stk[top - 1]))
                break;
            --top;
        }
        stk[++top] = i;
    }
    printf("%I64d\n", ans + res);
    return 0;
}

多一句嘴,网上三分什么的显然是错的,有兴趣的可以去叉一下。$\color{white}{\text{上面的代码开下 long long 就能过了}}$