Đập Bóng Bay Thu Được Điểm Lớn Nhất (Burst Balloons)
Bạn có N quả bóng bay được xếp thành một hàng ngang, quả thứ i có điểm số là Ai.
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: Interval DP, Reversed Thinking (Last Element Bursted).
Nội dung đề bài
Mô tả bài toán
Bạn có N quả bóng bay được xếp thành một hàng ngang, quả thứ i có điểm số là Ai.
Khi bạn đập vỡ quả bóng thứ i, bạn sẽ nhận được số điểm là: Aleft · Ai · Aright trong đó left và right là các quả bóng bay còn nguyên vẹn kề sát ngay bên trái và bên phải của quả bóng i.
- Nếu bên trái không còn quả bóng nào, quy ước Aleft = 1.
- Nếu bên phải không còn quả bóng nào, quy ước Aright = 1.
Sau khi quả bóng i bị nổ, các quả bóng hai bên sẽ tự động liền kề nhau.
Hãy tìm tổng số điểm lớn nhất có thể đạt được sau khi đã đập vỡ toàn bộ N quả bóng bay.
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. Bài này không yêu cầu viết hàm. - Không dùng
coutđể in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vàostdoutvà làm bài sai. - Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
- Dòng đầu chứa số nguyên N (1 ≤ N ≤ 300).
- Dòng thứ hai chứa N số nguyên A1, A2, …, AN (1 ≤ Ai ≤ 100).
Output
- In ra một số nguyên duy nhất là tổng điểm lớn nhất có thể đạt được.
Ràng buộc
- Thời gian chạy tối đa: 1000ms.
- Giới hạn bộ nhớ: 256MB.
- Dữ liệu đầu vào tuân thủ đúng định dạng và miền giá trị được mô tả.
Ví dụ 1
Input
4
3 1 5 8Output
167Giải thích
Dữ liệu kiểm thử mẫu và kết quả thực thi theo yêu cầu.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.