【BZOJ】1628 && 1683: [Usaco2007 Demo]City skyline 城市地平線（單調棧）

http://www.lydsy.com/JudgeOnline/problem.php?id=1628

http://www.lydsy.com/JudgeOnline/problem.php?id=1683

又是重複的題。。。。

單調棧維護遞減，然後相同的話矩形-1

The best part of the day for Farmer John's cows is when the sun sets. They can see the skyline of the distant city. Bessie wonders how many buildings the city has. Write a program that assists the cows in calculating the minimum number of buildings in the city, given a profile of its skyline.

The city in profile is quite dull architecturally, featuring only box-shaped buildings. The skyline of a city on the horizon is somewhere between 1 and W units wide (1 <= W <= 1,000,000) and described using N (1 <= N <= 50,000) successive x and y coordinates (1 <= x <= W, 0 <= y <= 500,000), defining at what point the skyline changes to a certain height.

An example skyline could be:

..........................

.....XX.........XXX.......

.XXX.XX.......XXXXXXX.....

XXXXXXXXXX....XXXXXXXXXXXX

and would be encoded as (1,1), (2,2), (5,1), (6,3), (8,1), (11,0), (15,2), (17,3), (20,2), (22,1).

給我們一個由一些矩形構造出來的圖，我們需要找到最少矩形的塊數來覆寫它 但是這個輸入比較奇怪,針對上圖,解釋如下: 1.1代表在第一列,有高度為1的矩形,矩形由"X"組成.這個矩形有多寬呢,這裡并沒有告訴你 2.2代表在第二列,有高度為2的矩形,這就間接告訴了你,前面那個矩形有多寬,寬度即2-1 5.1代表在第五列,有高度為1的矩形,這就間接告訴了你,前面那個矩形有多寬,寬度即5-2

This skyline requires a minimum of 6 buildings to form; below is one possible set of six buildings whose could create the skyline above:

.......................... ..........................

.....22.........333....... .....XX.........XXX.......

.111.22.......XX333XX..... .XXX.XX.......5555555.....

X111X22XXX....XX333XXXXXXX 4444444444....5555555XXXXX

XXXXXXXXXX....666666666666

* Line 1: Two space separated integers: N and W * Lines 2..N+1: Two space separated integers, the x and y coordinate of a point where the skyline changes. The x coordinates are presented in strictly increasing order, and the first x coordinate will always be 1.

* Line 1: The minimum number of buildings to create the described skyline.

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

6

  本文為部落客原創文章，未經部落客允許不得轉載。一經發現，必将追究法律責任。