Elearning CodePath – CTP Online Judge

Nhảy Lò Cò Dài Nhất

GEN002

🟢 Easy #Dynamic Programming #Binary Search

### 📌 Thông tin chung

Cho $N$ vòng tròn được đánh số từ $1$ đến $N$. Vòng tròn thứ $i$ được gán số nguyên dương $A_i$.

**Đồ thị (Di chuyển):**
* Một mũi tên (cạnh có hướng) được vẽ từ vòng tròn $i$ đến vòng tròn $k$, và từ vòng tròn $j$ đến vòng tròn $k$, nếu ba số $A_i, A_j, A_k$ thỏa mãn điều kiện:
$A_k = A_i + A_j$
* Người chơi chỉ được di chuyển theo hướng mũi tên.

Yêu cầu: Tìm **số lượng vòng tròn tối đa** mà người chơi có thể di chuyển qua trong một đường đi (Path) trên đồ thị này. Số lượng vòng tròn được đếm là số lượng đỉnh trong đường đi dài nhất.

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

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

* Dòng 1: Chứa số nguyên $N$.
* Dòng 2: Chứa dãy $N$ số nguyên dương $A_1, A_2, \dots, A_N$.

Giới hạn:
* $3 \le N \le 1000$.
* $1 \le A_i \le 10^9$.

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

Ghi ra file `LOCO.OUT` một số nguyên duy nhất là số lượng vòng tròn tối đa trên đường di chuyển tìm được.

---
### 🏷 Phân Subtask

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

---

✅ Đã AC: 1 / 8 submissions