T656528 反方向的钟 题解

· · 个人记录

n \le 5 & n \le 1000

不知道留给谁的

n \le 10^5

留给不会快速读入的人或实现不好的人

a_i \le 0

发现怎么穿越到过去都不优， 所以不穿越， 答案为数组的和

a_i \ge 0

发现从尾穿越到头最优，所以答案就是 (k + 1) \times \sum_{i=1}^n a_i

k = 0

发现无法穿越，答案就是数组和

k = 1

发现如果穿越答案的结构一定是一段前缀加一段后缀，且这段前后缀有交。发现这个问题可以转化为数组的和加上一段子段的和最大为多少，即求最大子段和的大小。 发现求 l 到 r 的子段和即为 \sum_{i = 1}^r a_i - \sum_{i = 1}^{l - 1} a_i 即前缀和的差。所以求最大子段和可以记录前缀的最小前缀和，并用当前前缀和减最小值更新答案。特殊的，若最大子段和小于零则无论如何穿越都不优，所以不穿越，答案为数组和。

正解

容易发现，题目没有限制 k 次穿越的位置，所以若我们发现了最优穿越点，我们可以在最优穿越点穿越 k 次，所以答案为数组和加 k 倍最大子段和。

code

#include<bits/stdc++.h>
using namespace std;
#define N 2000006
long long n, k, a[N], mn, mx;
int main() {
    scanf("%lld%lld", &n, &k);
    for(int i = 1; i <= n; ++i) {
        long long aa;
        scanf("%lld", &aa);
        a[i] = a[i - 1] + aa, mn = min(mn, a[i]), mx = max(mx, a[i] - mn);
    }
    printf("%lld", a[n] + k * mx);
    return 0;
}