Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

DTGAME - Tiền bạc luôn là thứ quý giá

       Tiền bạc vẫn luôn là thứ có giá trị đối với mỗi con người, kể cả với pirate. Vì vậy, khi hòn đảo xinh đẹp của tên cướp biển khét tiếng này sắp bị... giải tỏa, hắn đã tranh thủ vơ vét cho đến đồng tiền vàng cuối cùng. Trên hòn đảo có N mỏ vàng nằm cạnh nhau trên một đường thẳng, đánh số từ 1 đến N. Mỏ vàng i có giá trị là p_i. Đội thi công sẽ có nhiệm vụ san lấp hết N mỏ vàng này. Nhưng tại mỗi thời điểm, pirate cố gắng ngăn cản việc san lấp bằng cách xây một bức tường ngăn cách hai mỏ vàng liên tiếp nào đó, vậy là cụm mỏ còn lại được chia làm 2 phần. Đội thi công sẽ chọn một trong hai phần đó để san lấp hết, thế là pirate giữ lại được phần còn lại và hắn sẽ nhận được số đồng tiền vàng đúng bằng tổng giá trị của những mỏ còn lại đó. Công việc cứ tiếp tục cho đến khi chỉ còn lại một mỏ vàng duy nhất. Đội thi công biết điều đó, cho nên họ đã có chiến thuật san lấp để cực tiểu hóa số tiền của pirate. Với lòng tham không đáy, pirate quyết tâm lấy càng nhiều vàng càng tốt. Hãy giúp con người khốn khổ vì tiền này !

Input

Dữ liệu vào gồm nhiều dòng:

  • Dòng 1: Một số nguyên dương N (1 ≤ n ≤ 2000).
  • Dòng 2...n+1: Mỗi dòng ghi giá trị p_i của từng mỏ vàng theo thứ tự từ 1 đến n (1 ≤ p_i ≤ 1000).

Output

Dữ liệu ra gồm 1 dòng duy nhất ghi ra số đồng tiền vàng lớn nhất có thể vơ vét được.

Example

Input:
5
8
6
2
4
2

Output:10

Giải thích: Đầu tiền pirate chia mỏ vàng thành 2 phần [1,2] và [3,4,5]. Xe ủi sẽ san lấp phần [1,2] và pirate nhận được p_2 + p_3 + p_4 = 8 đồng tiền vàng. Tiếp theo chia [3,4,5] thành [3] và [4,5]. Xe ủi san lấp [4,5] và pirate thu thêm p_2 = 2 đồng tiền vàng. Công việc kết thúc vì chỉ còn 1 mỏ, vậy tổng cộng thu được là 8 + 2 = 10 đồng tiền vàng. Không có cách nào giúp hắn thu thêm tiền.


Được gửi lên bởi:Nguyễn Xuân Khánh
Ngày:2009-06-11
Thời gian chạy:0.178s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Sưu tầm

hide comments
2016-09-14 04:02:27
chặt nhị phân ez AC
2016-07-25 14:46:00
chặt nhị phân thôi mà :))
2016-06-17 10:19:01
Rất cám ơn! [$Zeus$]
2015-09-14 17:21:33
Tham khảo thuật toán : http://baitapspoj.blogspot.com/2015/09/DTGAME.html
2014-09-29 03:27:25 John and the cows
thanks bạn [$Zeus$]
2014-09-01 05:45:21 Stupid Dog
đề không rõ ràng :

với đoạn 5 2 3 , tất nhiên là chia 5 với 2 3 nhưng bên nào lấy 5 bên nào lấy 2 3.

Nếu muốn cướp phải lấy ít tiền nhất (theo nguyện vọng của đám thi công) thì tụi nó phải lấy 2 3.

Còn nếu như muốn cướp có nhiều tiền nhất "có thể" (theo ý của đề) thì tụi thi công phải lấy 5 (vì 5 = 2+3, nên xét trong trường hợp tụi thi công chỉ tối ưu hóa tại một thời điểm chứ không phải là lâu dài thì tụi nó có thể lấy 5 để cướp có thêm tiền tại thời điểm lúc sau như nguyện vọng đề cho

Hy vọng có thể giải thích rõ, hai kiểu đề sẽ cho hai cách code khác nhau


Last edit: 2014-09-02 03:46:22
2014-08-29 16:44:33 [$Zeus$]
Mình nộp loạn cả lên ... Bạn đọc đề cần chú ý là đội thi công sẽ chọn phướng án tối ưu, ko có nghĩa là cứ khu nào nhiều tiền hơn là lấy ngay mà khu nào có thể khai thác đến cuối cùng đc nhiều tiền hơn mới lấy.
2014-08-23 10:47:51 Lollipop
:v moi bua t thấy trong bạn bè m có anh NICK trên face rồi, cãi :3
2014-08-23 10:46:28 Thcs Ðặng Chánh Kỷ


Last edit: 2014-08-23 10:53:15
2014-08-23 10:42:20 Lollipop


Last edit: 2014-08-23 10:48:03
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.