LINEGAME - VOI09 Trò chơi với băng số
Giới hạn- Thời gian: 0.4s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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 a i , 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 ô i 1 , i 2 , ..., i k . Khi đó điểm số mà người chơi đạt được sẽ là:
- a i 1 - a i 2 + ... + (-1) k-1 a i k
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 ≤ 10 6 ) là số lượng ô của băng số;
- Dòng thứ hai chứa n số nguyên dương a 1 , a 2 , ..., a n ( a i ≤ 10 4 , 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ệu Kết quả 7 4 9 2 4 1 3 717
Ràng buộc: 60% số tests ứng với 60% số điểm của bài có 1 ≤ n ≤ 20.
- Người up: beo_map
- Nguồn bài: Thi HSG Quốc gia 2009