Problem Description:
In the
strong room of ABC bank there are N vaults arranged in a circle. The amount of
money inside each vault displayed on the door. You can empty any number of
vaults as long as you do not empty more than 2 out of any 5 adjacent vaults. If
you attempt to break more than 2 of any 5 adjacent vaults, an alarm sounds and
the sentry a sharp shooter will kill you instantly with his laser gun! Note
that as the vaults are arranged in a circle, the last vault is adjacent to the
first one.
The output
is the maximum amount of money that can be emptied without sounding the alarm
Input
Format:
The first
line contains an integer N which is the number of vaults. The next line has a
sequence of positive integers of length N, giving the amount of cash in its vaults
in order
Output
Format:
The maximum
amount of money that can be looted without sounding the alarm.
Constraints:
N<=50,
Amount in each vault <=50000
Example 1
Input
9
1000, 2000,
1000, 5000, 9000, 5000, 3000, 4000, 1000
Output
15000
Explanation
The vaults
1, 5, 6 are looted, giving a total loot of (1000+5000+9000)=15000
Example 2
Input
10
1000,2000,3000,5000,9000,7000,6000,4000,7000,5000
Output
26000
Explanation
There are 10
vaults arranged in a circle. The amounts in the vaults are 1000, 2000, ...
5000.
One way of
getting the maximum is to loot vaults 4, 5, 9 and 10 giving a total of 26000.
Hence the output is 26000. Note that no 5 adjacent vaults have more than 2
looted.
No comments:
Post a Comment