poj 3494 Largest Submatrix of All 1’s (单调栈)

poj 3494

题意:给出一个n*m个0-1图,求最大的全部由1组成的矩阵。

思路:同poj 1964,一共做n+2×m次单调栈。。。数组开小re一发。。某处stk忘记清空re 1发。。。智力-2.。。3A

 

 

poj 2796 Feel Good (前缀和,单调栈)

poj 2796

题意:给出一个人n(1E5)天的情绪值(0..1E6),一段时间的value的定义是这段时间的情绪之和*这段时间情绪的最小值。

现在求value的最大值,并且输出得到这个最大值的区间。

思路:单调栈。 考虑把每一天作为最小值的时候能向左向由延伸的最远的点的下标,两个方向各做一次单调栈来预处理。和的haunted前缀和搞下。。

然后最后想着了LL,但是读入的时候前缀和的那里忘了LL wa了一发。。。2A

 

 

poj 2082 Terrible Sets (前缀和,单调栈)

poj 2082 题目链接

题意:这道题简直就是。。。教给大家怎么把一句话把简单的题让人出得看不懂。。。真的一点意思都没有。给出n个矩形的宽度和高度,这些矩形并排顺次排列在x轴上,问最大面积。

思路:单调栈。 之前的最大矩形面积的宽度都是1.。这次不是1.。做个宽度的前缀和就好。。。1A

 

 

 

poj 1964 City Game(单调栈,输入挂)

poj 1964

题意:n*m的maze,由’R’和‘F’组成,现在要求找到面积最大的矩形,使得矩形中所有格子都是’F’。

思路:单调栈…一开始神tm tle….复杂度没问题啊。。。

结果看到有人说这题由于数据量比较大。。。scanf会超时。。。所以要用输入挂。。。。。getchar什么的。。。

poj竟然也卡读入。。。人性呢。。。。

改了输出以后再交wa了。

发现想错了,我是写了从(i,j)到两个方向能到的最大距离。。但是这样写有些点上的情况是没有考虑到的。。比如如果(i+1,j+1)上的点是’R’,实际上是不可以构成l*r的矩形的(l>=2&r>=2)。。。但是我这样做无法体现。

改了下,变成:

仍然对于每行做一次单调栈,预处理出点(i,j)能往右的最远距离a[i][j]。

然后观察一下。。。如果我把每一列分别看成x轴,那a[i][j]不就是矩形的高度了吗。。。

那我要求的不又变成了最大矩形面积了吗。。。

于是接下来对于每一列,做上下两个方向的单调栈得到(i,j)上下能延伸到的最远距离。

(i,j)点所在的矩形面积就是 (r[i][j]-l[i][j]+1)*a[i][j];

再交,A了

 

 

poj 3250 Bad Hair Day(单调栈)

poj 3250

题意:

n头牛排成一列,第n只牛在最前面,第1只牛在最后面。第i只牛能看到的牛的个数是,它前面的且没有被其他牛遮挡的牛的个数,遮挡的条件是高度大于或者相同。现在问所有牛能看到的牛的个数的和。

思路:单调栈。具体见代码。1A.

 

 

poj 2559 Largest Rectangle in a Histogram (单调栈)

poj 2559

题意:给定从左到右多个矩形,已知这此矩形的宽度都为1,长度不完全相等。这些矩形相连排成一排,求在这些矩形包括的范围内能得到的面积最大的矩形,求该面积。所求矩形可以横跨多个矩形,但不能超出原有矩形所确定的范围。

思路:单调栈。。。好久没写了,感觉之前一直也没有完全掌握单调栈的技巧。这回一定要掌握。

对于这道题,我们对于每个位置i,用两个单调栈维护出最左边和最右边最远能到达的位置。然后扫一遍更新最大值。

单调栈部分我用了stl 的stack

细节见注释

 

BZOJ 1660: [Usaco2006 Nov]Bad Hair Day 乱发节 (单调栈)

1660: [Usaco2006 Nov]Bad Hair Day 乱发节

Time Limit: 2 Sec  Memory Limit: 64 MB
Submit: 872  Solved: 415
[Submit][Status][Discuss]

Description

Input

* Line 1: 牛的数量 N。

* Lines 2..N+1: 第 i+1 是一个整数,表示第i头牛的高度。

Output

* Line 1: 一个整数表示c[1] 至 c[N]的和。

Sample Input

6
10
3
7
4
12
2

输入解释:

六头牛排成一排,高度依次是 10, 3, 7, 4, 12, 2。

Sample Output

5

3+0+1+0+1=5

HINT

Source

思路:裸的单调栈。

 

BZOJ 1657: [Usaco2006 Mar]Mooo 奶牛的歌声 (单调栈)

1657: [Usaco2006 Mar]Mooo 奶牛的歌声

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 634  Solved: 447
[Submit][Status][Discuss]

Description

Farmer John’s N (1 <= N <= 50,000) cows are standing in a very straight row and mooing. Each cow has a unique height h in the range 1..2,000,000,000 nanometers (FJ really is a stickler for precision). Each cow moos at some volume v in the range 1..10,000. This “moo” travels across the row of cows in both directions (except for the end cows, obviously). Curiously, it is heard only by the closest cow in each direction whose height is strictly larger than that of the mooing cow (so each moo will be heard by 0, 1 or 2 other cows, depending on not whether or taller cows exist to the mooing cow’s right or left). The total moo volume heard by given cow is the sum of all the moo volumes v for all cows whose mooing reaches the cow. Since some (presumably taller) cows might be subjected to a very large moo volume, FJ wants to buy earmuffs for the cow whose hearing is most threatened. Please compute the loudest moo volume heard by any cow.

Farmer John的N(1<=N<=50,000)头奶牛整齐地站成一列“嚎叫”。每头奶牛有一个确定的高度h(1<=h<=2000000000),叫的音量为v (1<=v<=10000)。每头奶牛的叫声向两端传播,但在每个方向都只会被身高严格大于它的最近的一头奶牛听到,所以每个叫声都只会 被0,1,2头奶牛听到(这取决于它的两边有没有比它高的奶牛)。 一头奶牛听到的总音量为它听到的所有音量之和。自从一些奶牛遭受巨大的音量之后,Farmer John打算买一个耳罩给被残害得最厉 害的奶牛,请你帮他计算最大的总音量。

Input

* Line 1: A single integer, N.

* Lines 2..N+1: Line i+1 contains two space-separated integers, h and v, for the cow standing at location i.

第1行:一个正整数N.

第2到N+1行:每行包括2个用空格隔开的整数,分别代表站在队伍中第i个位置的奶牛的身高以及她唱歌时的音量.

Output

* Line 1: The loudest moo volume heard by any single cow.

队伍中的奶牛所能听到的最高的总音量.

Sample Input

3
4 2
3 5
6 10

INPUT DETAILS:

Three cows: the first one has height 4 and moos with volume 2, etc.

Sample Output

7

HINT

队伍中的第3头奶牛可以听到第1头和第2头奶牛的歌声,于是她能听到的总音量为2+5=7.虽然她唱歌时的音量为10,但并没有奶牛可以听见她的歌声.

Source

Silver

 

思路:窝想到了是单调栈。。。但是细节想不清楚。。大抵还是对单调栈不够熟悉吧

 

BZOJ 1628: [Usaco2007 Demo]City skyline (单调栈)

1628: [Usaco2007 Demo]City skyline

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 396  Solved: 317
[Submit][Status][Discuss]

Description

Input

第一行给出N,W
第二行到第N+1行:每行给出二个整数x,y,输入的x严格递增,并且第一个x总是1

Output

输出一个整数,表示城市中最少包含的建筑物数量

Sample Input

10 26
1 1
2 2
5 1
6 3
8 1
11 0
15 2
17 3
20 2
22 1

INPUT DETAILS:

The case mentioned above

Sample Output

6
思路:我是正着做的,判断条件没有问题,但是细节不好处理,一直WA..大概是有什么地方没想到? 正解是单调栈。
转载一段题解:

答案的上限 肯定是 n, 何时会减一呢? 当有两座楼高度相等且它们的中间没有比它们低的楼。

所以要维护的是一个单调递增的序列, 每次弹出比它大的直到遇到一个和它相等的, 没有相等的话就把 它加入这个序列中。

实现很简单。

codeforces 442C. Artem and Array

C. Artem and Array
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Artem has an array of n positive integers. Artem decided to play with it. The game consists of n moves. Each move goes like this. Artem chooses some element of the array and removes it. For that, he gets min(a, b) points, where a and b are numbers that were adjacent with the removed number. If the number doesn’t have an adjacent number to the left or right, Artem doesn’t get any points.

After the element is removed, the two parts of the array glue together resulting in the new array that Artem continues playing with. Borya wondered what maximum total number of points Artem can get as he plays this game.

Input

The first line contains a single integer n (1 ≤ n ≤ 5·105) — the number of elements in the array. The next line contains n integers ai(1 ≤ ai ≤ 106) — the values of the array elements.

Output

In a single line print a single integer — the maximum number of points Artem can get.

Sample test(s)
input

output

input

output

input

output

 

 

并不会做.

接触了一个交单调栈的东西…

又是单调栈又是单调队列

是时候仔细了解下了.