LINEGAME spoj – VOI09 Trò chơi với băng số

Nguồn đề bài: http://vn.spoj.com/problems/LINEGAME/

1. Đề bài LINEGAME spoj

Trò chơi với băng số là trò chơi tham gia trúng thưởng được mô tả như sau: Có một băng hình chữ nhật được chia ra làm n ô vuông, đánh số từ trái qua phải bắt đầu từ 1. Trên ô vuông thứ i người ta ghi một số nguyên dương ai, i = 1, 2, …, n. Ở một lượt chơi, người tham gia trò chơi được quyền lựa chọn một số lượng tùy ý các ô trên băng số. Giả sử theo thứ tự từ trái qua phải, người chơi lựa chọn các ô i1, i2, …, ik. Khi đó điểm số mà người chơi đạt được sẽ là:

  • ai1 – ai2 + … + (-1)k-1aik

Yêu cầu: Hãy tính số điểm lớn nhất có thể đạt được từ một lượt chơi.

Dữ liệu

  • Dòng đầu tiên chứa số nguyên dương n ( n ≤ 106 ) là số lượng ô của băng số;
  • Dòng thứ hai chứa n số nguyên dương a1, a2, …, an ( ai ≤ 104, i = 1, 2, …, n ) ghi trên băng số. Các số liên tiếp trên cùng dòng được ghi cách nhau bởi ít nhất một dấu cách.

Kết quả

  • Một số nguyên duy nhất là số điểm lớn nhất có thể đạt được từ một lượt chơi.

Ví dụ

Dữ liệuKết quả
7
4 9 2 4 1 3 7
17

Ràng buộc: 60% số tests ứng với 60% số điểm của bài có 1 ≤ n ≤ 20.

==============================

bài này sử dụng QHĐ:

2. code tham khảo LINEGAME spoj pascal , c++:

 

3 thoughts on “LINEGAME spoj – VOI09 Trò chơi với băng số

Trả lời

Thư điện tử của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *