POJ 2796 Feel Good 【单调栈】

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

【题意】

给出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;
}
Kar PUC Biology Ques 说:
2022年9月20日 22:40

PUC Question Paper 2023 for Kar 1st & 2nd PUC Biology Model Paper 2023 Pdf Download with Answer Solutions for Theory, Objective type Multiple Choice Questions for Kannada Medium & English Medium students with important Questions. Kar PUC Biology Question Paper Biology is one of the most important subjects to Pre University Education (PUE) 1st and 2nd year Science stream students, and biology is a related subject of natural science, every student of PUC I & PUC II Science group Kannada medium and English medium student can download Karnataka 1st & 2nd Year PUC Biology Model Paper 2023.


登录 *


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