💻
Elearning
CodePath
Problems
Contests
Roadmap
🐱 Scratch
🔐 Login
Không chọn ba vị trí liên tiếp
DP1_03_no3sum
### Đề bài Cho dãy `n` số nguyên không âm. Chọn một số phần tử sao cho không có ba vị trí liên tiếp đều được chọn. Hãy tìm tổng lớn nhất của các phần tử được chọn. ### Dữ liệu vào Dòng 1 chứa `n`; dòng 2 chứa `a1..an`. ### Kết quả Tổng lớn nhất. ### Ràng buộc `1 ≤ n ≤ 2·10^5`, `0 ≤ ai ≤ 10^9`. ### Phân chia subtask | Subtask | Điểm | Ràng buộc | |---:|---:|---| | 1 | 30% | n ≤ 20 | | 2 | 30% | n ≤ 2000 | | 3 | 40% | n ≤ 2·10^5 | ### Ví dụ **Input** ```text 6 5 1 2 10 6 2 ``` **Output** ```text 22 ``` **Giải thích:** Có thể chọn các giá trị `5, 10, 6, 2` tại các vị trí `1,4,5,6` không hợp lệ vì 4–6 là ba vị trí liên tiếp. Phương án tối ưu hợp lệ đạt `22`, chẳng hạn chọn vị trí `1,3,4,5` hoặc `1,4,5,6`? Phương án sau cũng có ba vị trí 4,5,6 nên không hợp lệ; một phương án đúng là chọn `1,3,4,6`: `5+2+10+2=19`, và phương án `1,2,4,5`: `5+1+10+6=22`.
✅ Đã AC: 1 / 1 submissions
⬅ Contest
🚀 Nộp bài
💡 Gợi ý AI
📌 Bài kế
📋 Copy đề
⚙️
⬅ Contest
🚀 Nộp bài
💡 Gợi ý
📌 Bài kế
📋 Copy
📖 Hướng dẫn học tập
Học trò tri ân
☕ Một ly cà phê sẻ chia
Bạn bè ủng hộ
🍜 Một bát phở ấm lòng
💳 Quét mã ủng hộ tuỳ tâm nhé!
💬 Liên hệ Zalo!
Đóng