Cho một dãy số gồm phần tử, trong đó mỗi phần tử . Hai người chơi, gọi là Người thứ nhất () và Người thứ hai (), thực hiện xử lý các phần tử của dãy số theo thứ tự từ chỉ số 1 đến .
Quy tắc xử lý như sau:
Người thứ nhất () luôn là người bắt đầu trước. Hai người luân phiên nhau thực hiện lượt đi của mình.
Trong mỗi lượt, người chơi hiện tại phải chọn xử lý 1 hoặc 2 phần tử kế tiếp chưa được xử lý trong dãy.
Chi phí (Cost):
Nếu xử lý phần tử , chi phí cộng thêm là .
Nếu xử lý phần tử , chi phí cộng thêm luôn là .
Yêu cầu: Hãy tìm tổng chi phí tối thiểu để xử lý hết toàn bộ phần tử của dãy .
Dữ liệu:
Dòng đầu tiên chứa số nguyên () — số lượng bộ dữ liệu (test cases).
Mỗi bộ dữ liệu gồm hai dòng:
Dòng đầu chứa số nguyên ().
Dòng thứ hai chứa số nguyên ().
Tổng của trên tất cả các bộ dữ liệu không vượt quá .
Kết quả:
Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất là tổng chi phí tối thiểu đạt được.
Ví dụ:
Dữ liệu:
2
8
1 0 1 1 0 1 1 1
5
1 1 1 1 1
Kết quả:
2
2
Giải thích:
Ví dụ 1: Một chiến thuật tối ưu là: xử lý , xử lý , xử lý , xử lý , xử lý , xử lý . Tổng chi phí: .
Ví dụ 2: xử lý , xử lý , xử lý , xử lý . Chi phí: .
Giới hạn:
Subtask #1 (20% số điểm): và tổng .
Subtask #2 (15% số điểm): với mọi .
Subtask #3 (25% số điểm): và tổng .
Subtask #4 (40% số điểm): Không có ràng buộc bổ sung.
