HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


50674 - Collecting Eggs

Guest
• Review clarifications (1)

Section problems

• 50672 - Math and Soldiers
• 50671 - Phalanx
• 50842 - Minimum Sum Triangle - DP
• 50676 - Cinema Millennium
• 50678 - The Jumping Rabbit
• 51149 - One Piece Arena
• 50485 - Center of gravity of a plate
• 50674 - Collecting Eggs
• 50677 - The Cottage
• 50675 - Kruja Boys
• 50679 - Jetpack Hurdle Jumping
• 50673 - DNA Testing
• 50997 - Dynamic Knights
• 50936 - Saving the Soldiers
• 50979 - Minimum access cost for BST
• 51062 - Fish Pond II

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Osman Ay.

Collecting Eggs

Farmer George has a chicken farm. The chickens live in a hen house. There are N nesting-boxes where the chickens lay their eggs. These nesting-boxes are numbered from 1 to N consecutively. The Kth nesting-box is neighboring with K-1th and K+1th nesting-boxes.

The chickens lay their eggs in any of the nesting-boxes. Thus, each morning there can be different numbers of eggs in the boxes, and some boxes can be empty.

Farmer George uses a robot to collect the eggs in the nesting-boxes. The robot collects the eggs every morning and it has been programmed as follows:

  • It enters a box only once and picks all the eggs there.
  • When it takes the eggs from a box, it takes the eggs from two neigbouring nesting-boxes.
  • When the eggs from two consecutive boxes have been taken, the next one must be skipped.
  • It can skip as many boxes as it wishes.

Question:
To help farmer George, write a program that calculates the maximum number of eggs that can be gathered by the robot.

Input specification
The first line of the input has an integer N (2 ≤ N ≤ 2500) representing the number of the nesting-boxes. In the second line, there are N integers (each in the 0..100 range) representing number of the eggs in the nesting-boxes. The first number is for the first nesting-box, the second one is for the second nesting-box, and so on. The numbers in the second line are separated by a space.

Output specification
Show just one integer number: maximum number of eggs that can be gathered by the robot.

Sample Input I   
10
3 4 0 1 0 6 7 1 2 1
Sample Output I   
23

Explanation: (3+4) + (6+7) + (2+1) = 23

Time Limit: 0.1 second /test.


Для отправки решений необходимо выполнить вход.

www.contester.ru