单调栈

poj 3494 题意：给出一个n*m个0-1图，求最大的全部由1组成的矩阵。 思路：同poj 1964，一共做n+2×m次单调栈。。。数组开小re一发。。某处stk忘记清空re 1发。。。智力-2.。。3A

poj 2796 题意：给出一个人n（1E5）天的情绪值（0..1E6），一段时间的value的定义是这段时间的情绪之和*这段时间情绪的最小值。 现在求value的最大值，并且输出得到这个最大值的区间。

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

poj 1964 题意：n*m 的 maze，由 ‘R’ 和 ‘F’ 组成，现在要求找到面积最大的矩形，使得矩形中所有格子都是 ‘F’。 思路：单调栈。一开始神 tm TLE 了，复杂度明明没问题啊。 结果看到有人说这题数据量比较大，scanf 会超时，所以要用输入挂，getchar 什么的。

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

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

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.

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

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.