Elearning CodePath – CTP Online Judge

Các Biển Quảng Cáo

POSTERS

🟢 Easy #General #Dynamic Programming #Interval #Geometry #Optimization #Data Structure

### 📌 Thông tin chung

---
### 📝 Bài toán

Dọc theo đại lộ Tây-Đông là dãy $N$ ngôi nhà được xây dựng sát nhau, đánh số từ $1$ đến $N$ theo hướng Tây sang Đông. Tất cả các ngôi nhà đều quay mặt về phía Nam và có độ sâu bằng nhau.

Mặt phía Bắc (phía sau) của dãy nhà tạo thành một bức tường ghép từ $N$ hình chữ nhật. Ngôi nhà thứ $i$ có độ cao $h_i$ và chiều rộng $w_i$.

Chính quyền thành phố quyết định dán toàn bộ bức tường phía Bắc bằng các tấm poster (áp phích). Các tấm poster có dạng **hình chữ nhật** với các cạnh dọc và ngang (so với mặt đất). Các poster **không thể đặt chồng lên nhau** nhưng có thể có điểm chung (cạnh chung).

Yêu cầu: Tính số poster **tối thiểu** cần thiết để có thể che phủ toàn bộ mặt phía Bắc này của dãy nhà.

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `POSTERS.INP`:

* Dòng đầu tiên: Ghi $N$ là số ngôi nhà.
* $N$ dòng tiếp theo: Dòng thứ $i$ ghi hai số nguyên $w_i$ và $h_i$ là chiều rộng và chiều cao của ngôi nhà thứ $i$.

Giới hạn:
* $1 \le N \le 250000$.
* $1 \le w_i, h_i \le 10^6$.

---
### 📤 Định dạng Đầu ra

Ghi ra file `POSTERS.OUT` một số nguyên duy nhất là số poster tối thiểu tìm được.

---
### ✨ Ví dụ

| Input (`POSTERS.INP`) | Output (`POSTERS.OUT`) | 
| :--- | :--- | :--- |
| `5` `1 2` `1 3` `2 2` `2 5` `1 4` | `4` |

Giải thích (Dựa trên hình minh họa):
Dãy nhà gồm 5 phần. Chiều rộng của bức tường là $1+1+2+2+1 = 7$.
Các hình chữ nhật có độ cao: $2, 3, 2, 5, 4$.
1.  Poster 1: Che phủ $(1, 2), (3, 2)$ và phần dưới $(2, 3)$. (Che phủ chiều cao 2).
2.  Poster 2: Che phủ phần còn lại của $(2, 3)$, tức là chiều cao $3-2=1$.
3.  Poster 3: Che phủ phần còn lại của $(4, 5)$, tức là chiều cao $5-2=3$.
4.  Poster 4: Che phủ phần còn lại của $(5, 4)$, tức là chiều cao $4-2=2$.
Tổng số poster tối thiểu là $4$.

---
### 🏷 Phân Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N \le 5000$ | $40\%$ |
| 2 | $N \le 250000$ | $60\%$ |

---

✅ Đã AC: 0 / 0 submissions