Question

In the strong room of ABC bank there are N vaults in a row. 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. For example, of the vaults 1, 2, 3, 4, 5, if you empty 4 and 5, then you can not empty any of the vaults 6, 7 or 8 but you can empty 9th vault. 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! The output is the maximum amount of money that can be emptied without sounding the alarm Input 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 the vaults in order Output 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: One possible set of vaults to be looted to get the maximum possible are vaults 4, 5, 9 are looted, giving a total loot of (5000+9000+1000)=15000. Hence the output is 15000. Example 2 Input: 10 5000,7000,3000,5000,9000,7000,6000,4000,7000,5000 Output: 28000 Explanation: One possible set of vaults to be looted are (2, 5, 9, 10) Note that no set of five consecutive vaults has more than two vaults looted. The total looted is (7000 + 9000 + 7000 + 5000=28000). The out put is hence 28000.

Answer 1

#include<iostream> #define MAX(a, b) (((a)>(b))?(a):(b)) using namespace std; int main() { int N; int v[50]; int f00000[51]; int f00001[51]; int f00010[51]; int f00011[51]; int f00100[51]; int f00101[51]; int f00110[51]; int f01000[51]; int f01001[51]; int f01010[51]; int f01100[51]; int f10000[51]; int f10001[51]; int f10010[51]; int f10100[51]; int f11000[51]; cin >> N; for (int i = 0; i < N; i++) { cin >> v[i]; } if (N < 5) { v[N] = v[N + 1] = v[N + 2] = v[N + 3] = v[N + 4] = 0; } // initializing f00000[5] = 0; f00001[5] = v[4]; f00010[5] = v[3]; f00011[5] = v[3] + v[4]; f00100[5] = v[2]; f00101[5] = v[2] + v[4]; f00110[5] = v[2] + v[3]; f01000[5] = v[1]; f01001[5] = v[1] + v[4]; f01010[5] = v[1] + v[3]; f01100[5] = v[1] + v[2]; f10000[5] = v[0]; f10001[5] = v[0] + v[4]; f10010[5] = v[0] + v[3]; f10100[5] = v[0] + v[2]; f11000[5] = v[0] + v[1]; for (int n = 5; n < N; n++) { f00000[n + 1] = MAX(f00000[n], f10000[n]); f00001[n + 1] = MAX(f00000[n], f10000[n]) + v[n]; f00010[n + 1] = MAX(f00001[n], f10001[n]); f00011[n + 1] = MAX(f00001[n], f10001[n]) + v[n]; f00100[n + 1] = MAX(f00010[n], f10010[n]); f00101[n + 1] = MAX(f00010[n], f10010[n]) + v[n]; f00110[n + 1] = f00011[n]; f01000[n + 1] = MAX(f00100[n], f10100[n]); f01001[n + 1] = MAX(f00100[n], f10100[n]) + v[n]; f01010[n + 1] = f00101[n]; f01100[n + 1] = f00110[n]; f10000[n + 1] = MAX(f01000[n], f11000[n]); f10001[n + 1] = MAX(f01000[n], f11000[n]) + v[n]; f10010[n + 1] = f01001[n]; f10100[n + 1] = f01010[n]; f11000[n + 1] = f01100[n]; } int max = MAX(f00000[N], f00001[N]); max = MAX(max, f00010[N]); max = MAX(max, f00011[N]); max = MAX(max, f00100[N]); max = MAX(max, f00101[N]); max = MAX(max, f00110[N]); max = MAX(max, f01000[N]); max = MAX(max, f01001[N]); max = MAX(max, f01010[N]); max = MAX(max, f01100[N]); max = MAX(max, f10000[N]); max = MAX(max, f10001[N]); max = MAX(max, f10010[N]); max = MAX(max, f10100[N]); max = MAX(max, f11000[N]); cout << max << endl; system("pause"); }

Answer 2

Answer:

The maximum is 4 valuts

Explanation:

Input

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 the vaults in order

Output

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:

One possible set of vaults to be looted to get the maximum possible are vaults 4, 5, 9 are looted, giving a total loot of (5000+9000+1000)=15000. Hence the output is 15000.

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

5000,7000,3000,5000,9000,7000,6000,4000,7000,5000

Output:

28000

Explanation:

One possible set of vaults to be looted are (2, 5, 9, 10) Note that no set of five consecutive vaults has more than two vaults looted. The total looted is (7000 + 9000 + 7000 + 5000=28000). The out put is hence 28000.