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

Chúng tôi nhận thiết kế web công ty, thiết kế web thương mại điện tử, shop, thiết kế web blog cá nhân, viết phần mềm PC.

Liên hệ ngay: 035.870.8844 - Giá chỉ từ 2-3 triệu.

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

Email 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 *