- Mã:
- DAYCON2
- Tên:
- Dãy con không liên tiếp có tổng max
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- 4901103064
Cho một dãy số nguyên v có n phần tử và một số nguyên dương k. Bạn cần chọn một tập con các phần tử không liền kề sao cho tổng các phần tử được chọn là lớn nhất. Điều kiện quan trọng là: nếu bạn chọn phần tử tại vị trí i trong dãy, bạn không được chọn các phần tử tại các vị trí từ i+1 đến i+k-1.
Đầu vào:
-
Dòng đầu tiên chứa hai số nguyên n và k (1 ≤ n ≤ 1000, 1 ≤ k ≤ n), trong đó n là số lượng phần tử trong dãy và k là khoảng cách tối thiểu giữa các phần tử được chọn.
-
Dòng thứ hai chứa n số nguyên, là các phần tử của dãy v. Các phần tử này có thể âm hoặc dương.
Đầu ra:
-
In ra tổng lớn nhất mà bạn có thể đạt được từ các phần tử được chọn trong dãy.
-
In ra số lượng phần tử được chọn và các chỉ số của chúng (chỉ số bắt đầu từ 0).
-
Cuối cùng, in ra các giá trị của các phần tử đã chọn.
Input
Output
5 3
3 2 5 10 7
13
2
0 3
3 10
Theme :
Mời bạn soạn code