Elearning CodePath – CTP Online Judge

Cắt Thanh Sắt

DP005

🟢 Hard #Dynamic Programming

### 📌 Thông tin chung

---
### 📝 Định nghĩa

Cho một thanh sắt có độ dài nguyên dương $N$. Thanh sắt có thể được cắt thành các đoạn có độ dài nguyên dương $i$ bất kỳ ($1 \le i \le N$).

Với mỗi độ dài $i$, giá bán của đoạn thanh sắt dài $i$ là $P_i$.

---
### 📝 Yêu cầu

Hãy xác định cách cắt thanh sắt (cắt hoặc không cắt) sao cho tổng giá bán các đoạn thu được là lớn nhất.

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

* Dòng đầu chứa số nguyên $N$ — độ dài của thanh sắt ($1 \le N \le 1000$). (Giới hạn $N \le 1000$ được suy ra từ các gợi ý giải thuật).
* Dòng thứ hai chứa $N$ số nguyên $P_1, P_2, \dots, P_N$ — giá bán của thanh sắt dài từ 1 đến $N$ ($1 \le P_i \le 10000$).

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

Ghi ra một số nguyên duy nhất — tổng giá bán lớn nhất có thể thu được.

---
### ✨ Ví dụ

| Input | Output | Giải thích |
| :---: | :---: | :--- |
| `4` <br> `1 5 8 9` | `10` | Thanh sắt dài 4. Các độ dài có giá là: $P_1=1, P_2=5, P_3=8, P_4=9$. <br>Có thể cắt thành hai đoạn dài 2 (tổng giá $P_2 + P_2 = 5 + 5 = 10$). <br>Các phương án khác: $P_4=9$ (không cắt), $P_1+P_3=9$, $P_1+P_1+P_2=7$, $P_1+P_1+P_1+P_1=4$. Giá trị lớn nhất là 10. |

---
### 🏷 Ràng buộc

| Subtask | Giới hạn $N$ (Giả định) | Điểm | Kỹ thuật Gợi ý |
| :--- | :--- | :--- | :--- |
| $1$ | $N$ nhỏ (ví dụ $N \le 20$) | $10$ điểm | Quay lui (Backtracking), Đệ quy |
| $2$ | $N$ trung bình (ví dụ $N \le 50$) | $20$ điểm | Đệ quy có nhớ (Memoization/Top-down DP) |
| $3$ | $N \le 1000$ | $25$ điểm | Quy hoạch động bottom-up (1D mảng) |
| $4$ | $N \le 1000$ | $30$ điểm | Tối ưu truy cập bộ nhớ, tránh lặp, dùng mảng 1 chiều |

---

✅ Đã AC: 2 / 10 submissions