Tóm tắt đề bài

Cho mảng ~a~ gồm ~n~ phần tử dương. Với mọi ~x~ (~1 \le x \le \lfloor \frac {n + 1}{2} \rfloor~), ta cần chọn ra ~x~ phần tử sao cho tổng ~x~ phần tử đó là lớn nhất. Tuy nhiên ta không được chọn hai phần tử liên tiếp trong dãy gốc.

Giới hạn: ~n \le 200000~.

Subtask 1. ~n \le 20~

Duyệt nhị phân mọi cách chọn.

Độ phức tạp: ~O~ (~2^n \times n~).

Subtask 2. ~n \le 2000~, các phần tử là bằng nhau

Ta luôn có thể chọn ra ~k~ phần tử không kề nhau, và mọi cách chọn đều có tổng bằng nhau. Đáp án cho truy vấn thứ ~i~ sẽ là ~a_1 \times i~.

Độ phức tạp: ~O~ (~n~).

Subtask 3. ~n \le 2000~

Ta sẽ quy hoạch động.

Gọi ~dp[i][j]~ là tổng lớn nhất khi xét ~i~ phần tử đầu tiên, phần tử cuối cùng ta chọn là phần tử ~i~, và ta đã chọn tổng ~j~ phần tử.

Ta có công thức truy hồi:

• ~dp[i][1] = a[i]~ (cơ sở).
• ~dp[i][j] = max (dp[k][j - 1])~ với ~1 \le k \le i - 2~ để đảm bảo không chọn hai phần tử kề nhau.

Để xử lý công thức này, ta sử dụng prefix max.

Kết quả với truy vấn thứ ~i~ là ~max~ của các ~dp[x][i]~ với ~1 \le x \le n~.

Độ phức tạp: ~O~ (~n^2~).

Subtask 4. ~n \le 200000~

Nhận xét 1: Tập nghiệm của bài toán có dạng xâu nhị phân, tương ứng việc phần tử thứ ~i~ được chọn hay không.

Nhận xét 2: Khi ta cần tính kết quả với số phần tử ~x + 1~, mà ta đã biết kết quả của ~x~, ta có hai cách:

• Cách 1: Ta sẽ chọn thêm một phần tử trong tập ứng cử, mà không kề với bất kỳ phần tử nào ta đã chọn.
• Cách 2: Ta bỏ một phần tử ta đã chọn đi, sau đó ta cần chọn bù lại hai phần tử. Có thể chứng minh, ta luôn luôn chọn hai phần tử kề với phần tử ta vừa bỏ đi. Với cách chọn này, số phần tử tăng thêm là ~-1 + 2 = 1~, đúng như ta muốn.

Chứng minh:

• Ta sẽ chứng minh việc ta bỏ đi một phần tử ~i~, sau đó chỉ chọn một trong hai phần tử ~i - 1~ và ~i + 1~ là chưa tối ưu.
• Nếu ta chỉ lựa chọn một trong hai phần tử ~i - 1~ hoặc ~i + 1~, thì sẽ tồn tại một phần tử ~j~ khác mà ta sẽ chọn cùng. Lúc này, ta hoàn toàn đã chọn phần tử ~j~, và một trong hai phần tử ~i - 1~ hoặc ~i + 1~ ở truy vấn thứ ~x~ ngay trước truy vấn ta đang xét. Chắc chắn trong cách chọn ở truy vấn thứ ~x~ ngay trước truy vấn ta đang xét, chọn phần tử thứ ~i~ sẽ không là cách tối ưu.

Vì vậy, ta sẽ duy trì ~b_i~ là hiệu quả của việc đổi trạng thái của phần tử thứ ~i~. Việc đổi trạng thái này sẽ có nghĩa: bỏ đi nếu ta đang chọn phần tử ~i~, chọn thêm nếu ta chưa chọn.

Ban đầu, ~b_i = a_i~ toàn bộ, do toàn bộ các phần tử đều chưa được chọn.

Ta sẽ lặp từ ~1~ tới ~\lfloor \frac {n + 1}{2} \rfloor~, với mỗi bước ta cần làm như sau:

• Đầu tiên, chọn ra chỉ số ~i~ là chỉ số có giá trị ~b_i~ lớn nhất. Kết quả sẽ cộng thêm ~b_i~. Sau đó ta cần cập nhật lại các giá trị của tập ứng cử này.
• ~b_i~ sẽ được cập nhật thành ~-b_i + b_{i - 1} + b_{i + 1}~, như chứng minh ở trên, khi ta chuyển ~i~ thành không chọn, ta sẽ luôn chọn hai phần tử kề với nó.
• Tập ứng cử cần được xóa ~i - 1~ và ~i + 1~, do nếu ta cần chọn ~i - 1~ hoặc ~i + 1~, ta sẽ chỉ cần thực hiện "thay đổi" tập nghiệm ở vị trí ~i~ như đã nói ở trên.

Vấn đề đặt ra là quản lý tập ứng cử này, thay vì duyệt từ ~1~ tới ~n~ để tìm max. Để xử lý thao tác thêm và xóa một cách hợp lý, ta có thể sử dụng cấu trúc dữ liệu set trong C++.

Độ phức tạp: ~O~ (~n \times log~ ~n~).

Bạn đọc nên thử cài đặt theo hướng lặp để tìm phần tử tốt nhất, trước khi nâng cấp lên áp dụng set.