Gợi ý bài tập tính tổng các phần tử được chọn liên tiếp không quá k lần

[Wipad]

Vừa kết thúc kỳ thi nên Đức đã được giáo viên thưởng nóng, tuy nhiên vì giáo viên dạy Đức cũng là dân IT nên không dễ dàng cho Đức nhận được phần thưởng một cách đơn giản. Thể lệ trao thưởng như sau:
• Có 𝑛 món quà xếp thành một hàng ngang, các món quà có giá trị lần lượt là 𝑎1, 𝑎2, … , 𝑎𝑛 (các món quà có thể nhận giá trị âm là một hình phạt nếu Đức chọn sai).
• Đức được chọn bất kì món quà nào, hoặc không chọn, nhưng không được chọn quá 𝑘 món quà
liên tiếp.
Yêu cầu: Bạn hãy cùng Đức tính xem có thể chọn các món quà có tổng giá trị lớn nhất là bao nhiêu.

Input
• Dòng đầu ghi một số nguyên 𝑛 (𝑛 ≤ 10^5);
• Dòng thứ hai ghi 𝑛 số nguyên 𝑎1, 𝑎2, … , 𝑎𝑛(|𝑎𝑖| ≤ 10^9 , ∀𝑖 = 1,2, … , 𝑛) thể hiện giá trị của 𝑛 món quà.
• Dòng thứ 3 ghi số nguyên 𝑘.

Output
• In ra tổng giá trị các món quà lớn nhất mà bạn Đức có thể chọn.
Ràng buộc:
• Có 30% số test ứng với 30% số điểm thỏa mãn: 𝑘 = 1 và 𝑛 ≤ 20;
• 40% số test ứng với 40% số điểm thỏa mãn: 𝑘 = 2 và 𝑛 ≤ 20;
• 30% số test còn lại ứng với 30% số điểm thỏa mãn: 𝑘 = 2 và 𝑛 ≤ 10^5

Ví dụ 1
Input
5
6 9 1 3 5
2
Output
23
Giải thích:
Đức có thể chọn các món quà có giá trị là 6, 9, 3 và 5 có tổng bằng 23

Ví dụ 2
Input
5
6 9 1 -3 5
1
Output
14
Giải thích:
Đức có thể chọn các món quà có giá trị 9 và 5 có tổng bằng 14.

Chào mọi người, hôm nay làm đề gặp bài này mà chưa có bất kỳ ý tưởng nào để làm, nhờ mọi người giúp đỡ. Cảm ơn mọi người!

[tntxtnt]

viết công thức đệ quy lấy hoặc ko lấy thôi, thêm k vào nữa :V

gọi f(n, m) là tổng giá trị lớn nhất từ 1…n món quà, ko quá m món liên tiếp thì ta có công thức đệ quy là:

• nếu chọn lấy món quà thứ n: f(n, m) = a[n] + f(n - 1, m - 1)
• nếu chọn ko lấy món quà thứ n: f(n, m) = f(n - 1, k)
• nếu m = 0 thì f(n, 0) = f(n - 1, k) vì m=0 thì nghĩa là ko được chọn món hàng thứ n này nên bỏ qua
• nếu n = 0 thì f(0, m) = 0

vậy f(n, m) = max(a[n] + f(n - 1, m - 1), f(n - 1, k)) thôi :V

n <= 1e5, k <= 2 thì tạo mảng 2 chiều [100000][2] là 2e5 phần tử chạy lẹ thôi

[Wipad]

Subtask 1 và 2 em có lẽ làm được rồi, còn subtask 3 hơi khó hiểu, phiền anh nói cụ thể thêm 1 tí.
Với k = 1 thì em đoán công thức là f[n] = max(f[n], max(f[n-2], mx) + f[n]) với mx = max(f[n-3], f[n-4], …, f[1]); mảng f là mảng chứa input (giờ buồn ngủ quá nên mai mới test xem có đúng không )
Còn k = 2 thì em chịu @@

[tntxtnt]

k=2 thì nếu chọn phần tử cuối cùng thì bài toán f(m, n) trở thành a[n] + f(1, n-1), nếu ko chọn thì bài toán trở thành f(2, n-1) thôi :V

[tntxtnt]

vd mảng a = 6 9 1 3 5 và k = 2 (với a[1] = 6)
f(2, 5) = max(a[5] + f(1, 4), f(2, 4))
f(2, 4) = max(a[4] + f(1, 3), f(2, 3))
f(2, 3) = max(a[3] + f(1, 2), f(2, 2))
f(2, 2) = max(a[2] + f(1, 1), f(2, 1))
f(2, 1) = max(a[1] + f(1, 0), f(2, 0)) = max(6 + 0, 0) = 6
f(1, 1) = max(a[1] + f(0, 0), f(2, 0)) = max(6 + 0, 0) = 6
vậy f(2, 2) = max(9 + 6, 6) = 15
f(1, 2) = max(a[2] + f(0, 1), f(2, 1)) = max(9 + f(2, 0), 6) = max(9 + 0, 6) = 9
vậy f(2, 3) = max(1 + 9, 15) = 15
f(1, 3) = max(a[3] + f(0, 2), f(2, 2)) = max(1 + f(2, 1), 9) = max(1 + 6, 15) = 15
vậy f(2, 4) = max(3 + 15, 15) = 18
f(1, 4) = max(a[4] + f(0, 3), f(2, 3)) = max(3 + f(2, 2), 15) = max(3 + 15, 15) = 18
vậy f(2, 5) = max(5 + 18, 18) = 23

f(0, 3) nghĩa là chọn tối đa 0 phần tử liên tiếp từ đuôi mảng 6 9 1, nghĩa là phải bỏ qua a[3] là 1, khi này bài toán trở thành f(2, 2) là chọn tối đa 2 phần tử liên tiếp tính từ đuôi mảng 6 9. Từ m=0 nhảy lại thành m=k=2 thôi :V

bỏ qua thì reset lại m=k, lấy thì +a[n] và set m=m-1, m=0 thì bắt buộc phải bỏ.

nhận thấy f(m, n) lệ thuộc f(…, n-1) vậy tính ngược từ dưới lên i=1…n chỉ cần “mảng” k = 2 phần tử là đủ, vậy bài toán có thể tính trong O(nk) time và O(k) mem mà k=2 thì coi như O(n) time và O(1) mem hơn nữa có thể cũng ko cần lưu cái mảng a nữa vì truy cập a[i] theo thứ tự nên vừa đọc vừa tính luôn O(1) mem thật sự

[Wipad]

Cảm ơn anh nhiều, em làm được rồi