poj 遞增棧 POJ2796 區間最大參考值 3250牛的視野

poj 遞增棧 POJ2796 區間最大參考值 3250牛的視野

#include 
#include 
using namespace std;

const int N = 100005;

struct Elem
{
	long long height;
	long long width;
	int begin;
	int count;
};

Elem stack[N];
int top;

int main()
{
	int num, n;
	long long ans, tmp, tot;
	int ansbeg, ansend, count;
	scanf("%d", &n);
	top = 0;
	ans = 0;
	ansbeg = ansend = 1;
	for (int i = 0; i < n; ++i)
	{
		scanf("%d", &num);
		tmp = 0;
		count = 0;
		while (top > 0 && stack[top - 1].width >= num)
		{
			stack[top - 1].count += count;
			tot = (stack[top - 1].height + tmp) * stack[top - 1].width;
			if (tot > ans)
			{
				ans = tot;
				ansbeg = stack[top - 1].begin;
				ansend = ansbeg + stack[top - 1].count - 1;
			}
			tmp += stack[top - 1].height;
			count = stack[top - 1].count;
			--top;
		}
		stack[top].height = num + tmp;
		stack[top].width = num;
		stack[top].begin = i + 1 - count;
		stack[top].count = 1 + count;
		++top;
	}
	tmp = 0;
	count = 0;
	while (top > 0)
	{
		stack[top - 1].count += count;
		tot = (stack[top - 1].height + tmp) * stack[top - 1].width;
		if (tot > ans)
		{
			ans = tot;
			ansbeg = stack[top - 1].begin;
			ansend = ansbeg + stack[top - 1].count - 1;
		}
		tmp += stack[top - 1].height;
		count = stack[top - 1].count;
		--top;
	}
	printf("%lld\n%d %d\n", ans, ansbeg, ansend);
	return 0;
}

題解：給定一個數組，定義某個區間的參考值為：區間所有元素的和*區間最小元素。求該數組中的最大參考值以及對應的區間。

解題報告：（1）設某個區間所有元素的和為height，區間最小元素為width，則對於單個元素的區間，height = width = 元素的值。建立一個單調遞增的棧。

（2）棧中的每一個元素的height值等於前面比其大的和自身值的和；從第一個元素開始入棧，每個元素入棧之前必須先從棧頂開始刪除大於或等於它的元素，把刪除的所有元素的height累加到當前元素的height，然後把當前元素的值保存在width值中，這表示把當前元素前面比它大或相等的連續元素的值加起來，乘以它自己，也就是這段區間的參考值。

（3）每一次刪除元素都需要計算一個參考值，取參考值的最大值就是答案了。不過題目還要求給出對應區間的起點和終點，因此在棧的操作過程中還得記錄當前元素保存的區間的起點和大小，在更新參考值的過程中順便更新區間的起點和終點就可以了。

#include 
using namespace std;

const int maxn = 80005;
int stack[maxn],top = 0;//top指向當前元素下一個位置

int main()
{
    long long ans = 0;
    int i,n,tmp;
    cin >> n;
    for(i=0;i> tmp;
        while(top>0 && stack[top-1]<=tmp)
        {
            top--;
        }
        ans += top;
        stack[top++] = tmp;
    }
    cout << ans << endl;
}

題意：一群高度不完全相同的牛從左到右站成一排，每頭牛只能看見它右邊的比它矮的牛的發型，若遇到一頭高度大於或等於它的牛，則無法繼續看到這頭牛後面的其他牛。給出這些牛的高度，要求每頭牛可以看到的牛的數量的和。

解題報告：（1）把要求作一下轉換，其實就是要求每頭牛被看到的次數之和。這個可以使用單調棧來解決。

（2）從左到右依次讀取當前牛的高度，從棧頂開始把高度小於或等於當前牛的高度的那些元素刪除，此時棧中剩下的元素的數量就是可以看見當前牛的其他牛的數量。把這個數量加在一起，就可以得到最後的答案了。