28 August

单调队列复习。

投资 (invest)

给定一带符号整数数列，求长度为 \([s, e]\) 的子区间的和的最大值。（最大子段和）

降二维为一维，for循环枚举区间右端点。预处理前缀和，问题转化为找到最小的左端点。

使用单调队列维护查找范围内最小值。参看单调队列总结。

单调队列算法实现：

弹出单调队列左端的失效元素。

弹出单调队列右端的破坏单调性的元素。如在最小值单调队列中，剔除比即将加入的元素更大的元素，因为后者已对答案无未来贡献。（比前者先失效，未来不会是更小值。）

加入新元素。计算并统计当前单调队列维护的最优值。

int q[N], l, r;

int m=1;

int main() {

	n=read(), s=read(), e=read(); // s 区间最小长度, e 区间最大长度

	for (int i=1; i<=n; i++)

		a[i] += a[i-1] + read();

	for (int i=s; i<=n; i++) {

		while (l < r && i-q[l] > e)

            l++;

        while (l < r && a[i-s] < a[q[r-1]])

            r--;

        q[r++] = i-s;

        m=max(m, a[i] - a[q[l]]);

	}

	write(m);

	return 0;

}

巴特西

28 August

投资 (invest)

最新文章

热门文章