Để tính khối lượng táo nhiều nhất mà Long có thể ăn được, ta sẽ đi tính khối lượng táo ít nhất mà Vũ có thể ăn.

Đặt \(dp(i)\) là lượng táo ít nhất mà Vũ ăn được trong \(i\) quả táo đầu tiên. Đáp án bài toán chính là \(\sum\limits_{i=1}^{n} a_i - dp(n)\)

Subtask 1

Ta cập nhật mỗi \(dp(i)\) từ mọi \(dp(j)\) mà \(0 \le j < i\). Do đó ĐPT là \(O(n^2)\)

Subtask 2

Nhận thấy \(m \le 200, n\times m \le 2 \times 10^7\) và mọi \(a_i\) đều dương nên thực chất ta vẫn có thể duyệt trâu để tính \(dp(i)\) như trên trong ĐPT \(O(n \times m)\).
(Chỉ duyệt \(j\) từ \(i-1\) về \(max(0,i-m)\))

Subtask 3

Ta sử dụng các CTDL đặc biệt để tính \(dp(i)\). Về bản chất, ta vẫn xét tất cả mọi trường hợp và lấy ra Min, tuy nhiên việc này được thực hiện hiệu quả trong thời gian \(O(log_2(n))\).

Cụ thể, khi duyệt \(i\), ta sẽ duy trì một con trỏ \(L, 0 \le L < i, L\) bé nhất và đoạn \((L;i]\) có tổng không quá \(m\).

Có các trường hợp cập nhật QHĐ :

• Chọn nhóm \([L+1;i]\) : \(dp(i) = dp(L) + max(a[L+1 \rightarrow i])\)
• Chọn nhóm \([j;i]\) bất kì (\(j > L\)) mà \(a[k]\) là max đoạn \([j;i]\) : \(dp(i) = dp(j-1) + a[k]\)

Để xét các \(a[k]\) mà là max của một đoạn bất kì, ta sẽ dùng một stack lưu các số \(a\) giảm dần.
Khi đó, có thể lấy được vị trí \(j\) bé nhất mà \(a[j] \le a[k]\). Ta sẽ thêm \(dp(j-1) + a[k]\) vào CTDL, chẳng hạn như Segment Tree, MultiSet, hoặc Priority Queue.
Mỗi khi \(a[k]\) bị pop khỏi stack (tức \(a[k] \le a[i]\)), ta xóa giá trị \(dp(j-1) + a[k]\) ra khỏi CTDL.

Các bạn có thể tham khảo code mẫu của mình tại đây : https://imgur.com/a/SQC9SrS