Lutece 2150 拍照

题目链接: https://acm.uestc.edu.cn/problem/pai-zhao/description

分析:

假设sum数组为前缀和。

以Aj结尾的数列的最大值,即是sum[ j ] – min( sum[ j-m ] ~ sum[ j-1 ] ),当然中间有一些特例,但是大体上是这样的。

而维护区间最值,可以使用线段树。

代码:

#include<bits/stdc++.h>
using namespace std;
const long long MAXN = 100001;
long long a[MAXN],minnum[MAXN<<2];
void build(long long o, long long l, long long r)
{
	if (l == r)minnum[o] = a[l];
	else
	{
		long long m = l + ((r - l) >> 1);
		build(o << 1, l, m);
		build((o << 1) | 1, m + 1, r);
		minnum[o] = min(minnum[o<<1],minnum[(o<<1)|1]);
	}
}
long long query(long long o, long long l, long long r, long long ql, long long qr)
{
	long long nowmin = 1000000000000000ll;
	if (ql <= l && qr >= r)
	{
		return minnum[o];
	}
	long long m = l + ((r - l) >> 1);
	if (ql <= m)
	{
		nowmin = min(nowmin, query(o << 1, l, m, ql, qr));
	}
	if (qr >= m + 1)
	{
		nowmin = min(nowmin, query(o << 1 | 1, m + 1, r, ql, qr));
	}
	return nowmin;
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	long long n, m,linshi;
	cin >> n >> m;
	a[0] = 0;
	for (long long i = 1; i <= n; ++i)
	{
		cin >> linshi;
		a[i] = a[i - 1] + linshi;
	}
	build(1,1,n);
	long long maxnum = a[1];
	for (long long i = 2; i <= n; ++i)
	{
		if (i > m)
		{
			linshi = a[i] - query(1, 1, n,i - m, i - 1);
			if (linshi > maxnum)
			{
				maxnum = linshi;
			}
		}
		else
		{
			linshi = a[i] - min(query(1, 1, n, 1, i - 1),0ll);
			if (linshi > maxnum)
			{
				maxnum = linshi;
			}
		}
	}
	cout << maxnum;
	//system("pause");
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注