4945：[POI 2008] PLA-Postering

# [POI 2008] PLA-海报张贴 ## 题目描述 比特堡东区的所有建筑都按照古老的工艺建造：它们紧密相连，中间没有任何空隙。这些建筑形成了一长串高度各不相同的建筑群，从东延伸到西。 比特堡市长比泰萨尔决定用海报覆盖这一整排建筑的北墙面。比泰萨尔想要知道**覆盖整个北墙面所需的最少海报数量**。 海报是矩形，边为竖直和水平方向。海报**不能重叠**，但可以相邻（即边缘可以接触）。每张海报必须**完全贴在建筑墙面上**，且要把所有建筑的北墙面完全覆盖。 ### 任务 编写程序完成以下要求： - 从标准输入读取建筑信息； - 计算完全覆盖建筑北墙面所需的**最少矩形海报数量**； - 将结果输出到标准输出。 ## 输入格式 第一行输入一个整数 $n$（$1\le n\le 250\ 000$），表示建筑的数量。 接下来 $n$ 行，每行两个整数 $d_i$ 和 $w_i$（$1\le d_i,w_i\le 1\ 000\ 000\ 000$），用空格分隔，分别表示**第 $i$ 栋建筑的长度**和**高度**。 ## 输出格式 仅输出一行一个整数，表示覆盖所有建筑北墙面所需的最少海报数量。 ## 输入样例1： ``` 5 1 2 1 3 2 2 2 5 1 4 ``` ## 输出样例1： ``` 4 ``` ## 提示 （暂无提示） 标签：P3467|2008|POI（波兰）|单调栈 ## 来源 P3467|[POI 2008] PLA-Postering