Trọng số của dãy số

[Nobita004 (Kirito-kun)]

Trọng số của một dãy số nguyên a1, a2, . . , an được tính bằng:

• Hiệu của tổng các số có chỉ số lẻ và tổng các số có chỉ số chẵn

Ta có phép biến đổi dãy số như sau: Xóa đi một số phần tử để nhận được một dãy số mới.3

Yêu cầu: Cho dãy số nguyên a1, a2, . . , an, hãy biến đổi dãy để nhận được dãy số có trọng số nhỏ nhất.

Dữ liệu: Vào từ file văn bản WSEQ0.INP gồm hai dòng:

• Dòng 1: Chứa số nguyên dương n;
• Dòng 2: Chứa n số nguyên mô tả a1, a2, . . , an (|ai| ≤ 10^9)

Kết quả: Ghi ra file văn bản WSEQ0.OUT gồm một dòng: Ghi một số là trọng số nhỏ nhất của dãy tìm được.

Ví dụ:

WSEQ0.INP	WSEQ0.OUT
3 -1 2 5	-6

Ràng buộc:

• Subtask 1: 50% số điểm tương ứng với n ≤ 20;
• Subtask 2: 25% số điểm tương ứng với n ≤ 2000;
• Subtask 3: 25% số điểm tương ứng với n ≤ 200000;

Mọi người có thể cho em xin thuật toán để full bài này được không ạ? Em cảm ơn !

[rogp10]

Cái này dùng prefix sum vì suffix tính được từ prefix, và cũng cần prefix.