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

CPP

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

T656528 反方向的钟题解

文章操作

$n \le 5$ & $n \le 1000$

$n \le 10^5$

$a_i \le 0$

$a_i \ge 0$

$k = 0$

$k = 1$

正解

code

相关推荐

评论

T656528 反方向的钟题解

文章操作

n≤5n \le 5n≤5 & n≤1000n \le 1000n≤1000

n≤105n \le 10^5n≤105

ai≤0a_i \le 0ai​≤0

ai≥0a_i \ge 0ai​≥0

k=0k = 0k=0

k=1k = 1k=1

正解

code

相关推荐

评论

$n \le 5$ & $n \le 1000$

$n \le 10^5$

$a_i \le 0$

$a_i \ge 0$

$k = 0$

$k = 1$