POJ 2796 Feel Good 【单调栈】

tonyfang posted @ 2016年7月23日 16:12 in poj with tags C++ OI , 199 阅读

【题意】

给出n和a[1...n],求出一对l,r使得sum[l, r] * min[l, r]最大。

【题解】

往两边单调栈求出第一个比当前小的数的位置。

然后随便做啦,O(n)

 

# include <stdio.h>
# include <iostream>
# include <string.h>
using namespace std;
int n, a[100100], last[100100], next[100100];
int st[100100], stn=0;
int stw[100100], l, r;
long long s[100100], maxx=-99999999;
int main() {
	scanf("%d", &n);
	for (int i=1; i<=n; ++i) {
		scanf("%d", &a[i]);
		s[i] = s[i-1] + a[i];
	}
	for (int i=1; i<=n; ++i) {
		if(a[i] > st[stn]) {
			st[++stn] = a[i];
			last[i] = stw[stn-1];
			stw[stn] = i;
		} else {
			while(a[i] <= st[stn] && stn != 0) --stn;
			if(stn == 0) last[i] = 0;
			else last[i] = stw[stn];
			st[++stn] = a[i];
			stw[stn] = i;
		}
	}
	stn = 0;
	memset(st, 0, sizeof(st));
	memset(stw, 0, sizeof(stw));
	for (int i=n; i>=1; --i) {
		if(a[i] > st[stn]) {
			st[++stn] = a[i];
			next[i] = stw[stn-1];
			stw[stn] = i;
		} else {
			while(a[i] <= st[stn] && stn != 0) --stn;
			if(stn == 0) next[i] = n+1;
			else next[i] = stw[stn];
			st[++stn] = a[i];
			stw[stn] = i;
		}
	}
	for (int i=1; i<=n; ++i) {
		//printf("%d %d\n", last[i], next[i]);
		long long t = (long long)a[i] * (s[next[i]-1] - s[last[i]]);
		if(t>maxx) {
			maxx=t;
			l=last[i]+1;
			r=next[i]-1;
		}
	}
	cout << maxx << endl;
	cout << l << ' ' << r << endl;
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter