UVA1619 感觉不错 Feel Good

预处理+DP \(O(n)\) 。

我们记：

• n 为数列的长度
• \(a_i\) 表示数列的第 i 号元素
• \(l_i\) 表示从第 i 号元素向左最多延伸到哪里（使得 \(a_i\) 始终是 \(\min_{j=l_i}^{i} a_j\)）
• \(r_i\) 表示从第 i 号元素向右最多延伸到哪里（使得 \(a_i\) 始终是 \(\min_{j=i}^{r_i} a_j\)）
• 题目中子区间的数字和乘上子区间中的最小值为这个子区间的权值

这样以 \(a_i\) 号元素为最小值的区间的权值最大就是 \(a_i \times \sum_{j=l_i}^{r_i}a_j\)

前面部分显然 \(O(1)\) ，前缀和可以让后面的部分变成 \(O(1)\)，所以总复杂度为 \(O(n)\)。

Code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100005
int n, a[N], b[N], l[N], r[N];
signed main()
{
	int T = 0;
	while(scanf("%lld", &n) != EOF && n)
	{
		if(T++)
		{
			putchar(10);
		}
		for(int i = 1; i <= n; i++)
		{
			scanf("%lld", &a[i]);
			b[i] = b[i - 1] + a[i];
		}
		for(int i = 1; i <= n; i++)
		{
			if(i == 1)
			{
				l[i] = 1;
				continue;
			}
			int pos = i - 1;
			for(; pos >= 1; pos--)
			{
				if(a[i] > a[pos])
				{
					break;
				}
				else
				{
					pos = l[pos];
				}
			}
			l[i] = pos + 1;
		}
		for(int i = n; i >= 1; i--)
		{
			if(i == n)
			{
				r[i] = n;
				continue;
			}
			int pos = i + 1;
			for(; pos <= n; pos++)
			{
				if(a[i] > a[pos])
				{
					break;
				}
				else
				{
					pos = r[pos];
				}
			}
			r[i] = pos - 1;
		}
		int ans = 0, ansl = 1, ansr = 1;
		for(int i = 1; i <= n; i++)
		{
			if(ans < a[i] * (b[r[i]] - b[l[i] - 1]))
			{
				ans = a[i] * (b[r[i]] - b[l[i] - 1]);
				ansl = l[i];
				ansr = r[i];
			}
			else if(ans == a[i] * (b[r[i]] - b[l[i] - 1]))
			{
				if(ansr - ansl + 1 > r[i] - l[i] + 1)
				{
					ansl = l[i];
					ansr = r[i];
				}
				else if(ansr - ansl + 1 == r[i] - l[i] + 1)
				{
					if(l[i] < ansl)
					{
						ansl = l[i];
						ansr = r[i];
					}
				}
			}
		}
		printf("%lld\n", ans);
		printf("%lld %lld\n", ansl, ansr);
	}
	return 0;
}