洛谷P1901发射站

一道单调栈裸题，主要是用单调栈维护单调性，和单调队列都可以在\(O(n)\)的时间内得出单调最大值或最小值，要比堆要快。

这个题可以用h来当做单调栈的使用对象，即用单调栈来维护高度，高度是越在栈深处越大，元素下标是越在栈深处越小。

\(Code\):

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cstdio>

#include <cstdlib>

#include <stack>

#define N 1100001

using namespace std;

struct da {

	int H, V, MAXN;//H,V分别代表本身的高度，MAXN代表以i这个发射站所得到的最大值。

} stac[N];

int n, maxn, top, now;

int main()

{

 	scanf("%d", &n);

 	for (int i = 1, h, v; i <= n; i++)

 	{

 		scanf("%d%d", &h, &v);now = 0;

 		while (top && stac[top].H < h)//寻找第一个大于等于h的栈内元素.而且不仅要将小于h的栈内元素出栈 ，而且还要把这第一个元素出栈，因为该元素已经不可以在向右发挥作用了，且右边的发射站也肯定不会向左给该元素发挥作用了，那它就没用了。

 				now += stac[top--].V;

 		if (stac[top].H > h)

			stac[top].MAXN += v;

 		stac[++top].H = h, stac[top].V = v, stac[top].MAXN = now;

 		if (top == 1)

 		maxn = max(maxn, stac[top].MAXN);

 		else//因为top元素和top-1元素在此次循环中都增加了，但不知道那个大，所以要判断。

 		maxn = max(maxn, max(stac[top].MAXN, stac[top - 1].MAXN));

 	}

 	printf("%d", maxn);

}

巴特西

洛谷P1901发射站

最新文章

热门文章