Tổng lớn nhất khi không lấy hai phần tử kề nhau
Cho một dãy số dương, ta muốn chọn ra một nhóm phần tử có tổng lớn nhất nhưng không được chọn
Tiến độ của tôi ở bài này
Điểm và code bạn nộp đượ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: cpp-basics, arrays.
Nội dung đề bài
Mô tả bài toán
Cho một dãy số dương, ta muốn chọn ra một nhóm phần tử có tổng lớn nhất nhưng không được chọn hai phần tử nằm sát nhau. Đây là dạng "quy hoạch động một chiều" đơn giản nhất: tại mỗi vị trí chỉ có hai lựa chọn là bỏ qua hoặc lấy kèm tổng tốt nhất của vị trí cách đó một ô.
Yêu cầu
Cho n số nguyên không âm a1, a2, ..., an. Hãy chọn một tập chỉ số không chứa hai chỉ số liên tiếp nhau sao cho tổng các giá trị được chọn là lớn nhất. In ra tổng lớn nhất đó.
Quy ước nộp bài
Nộp tệp solution.cpp đọc dữ liệu từ stdin và ghi kết quả ra stdout. Chỉ in một số nguyên trên một dòng, không kèm chữ hay dấu cách thừa.
Input
- Dòng thứ nhất: số nguyên n (1 <= n <= 50).
- Dòng thứ hai: n số nguyên a1 ... an cách nhau bởi dấu cách (0 <= ai <= 1000).
Output
- Một số nguyên trên một dòng là tổng lớn nhất chọn được.
Ràng buộc
- Không được chọn hai chỉ số liên tiếp; các chỉ số còn lại tuỳ ý.
- Thời gian cho mỗi bộ dữ liệu là 1 giây.
Ví dụ 1
Input
4
1 2 3 1
Output
4
Ví dụ 2
Input
5
2 7 9 3 1
Output
12
Giải thích
Chọn a1 = 1 và a3 = 3 được tổng 4, còn a2 + a4 = 3 nhỏ hơn. In ra:
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.
