Last active
August 27, 2020 16:15
-
-
Save MostafijurJ/561560b2153dabb0d9e8210ec9b6a67a to your computer and use it in GitHub Desktop.
Monkey Banana Problem of LightOJ
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Problem: You are in the world of mathematics to solve the great "Monkey Banana Problem". | |
It states that, a monkey enters into a diamond shaped two dimensional array and can jump in any of the adjacent cells down from its current position (see figure). | |
While moving from one cell to another, the monkey eats all the bananas kept in that cell. | |
The monkey enters into the array from the upper part and goes out through the lower part. | |
Find the maximum number of bananas the monkey can eat. | |
Input: Input starts with an integer T (≤ 50), denoting the number of test cases. Every case starts with an integer N (1 ≤ N ≤ 100). It denotes that, | |
there will be 2*N - 1 rows. The ith (1 ≤ i ≤ N) line of next N lines contains exactly i numbers. | |
Then there will be N - 1 lines. The jth (1 ≤ j < N) line contains N - j integers. | |
Each number is greater than zero and less than 215 | |
Output: For each case, print the case number and maximum number of bananas eaten by the monkey. | |
Sample input: | |
2 | |
4 | |
7 | |
6 4 | |
2 5 10 | |
9 8 12 2 | |
2 12 7 | |
8 2 | |
10 | |
2 | |
1 | |
2 3 | |
1 | |
output: | |
Case 1: 63 | |
Case 2: 5 | |
Solution: | |
#include<bits/stdc++.h> | |
using namespace std; | |
long long int a[500][500],dp[500][500]; | |
int main() | |
{ | |
int T,kase=0; | |
scanf("%d",&T); | |
while(T--) | |
{ | |
int i,j,k,N,y; | |
scanf("%d",&N); | |
memset(a,0,sizeof(a)); | |
memset(dp,0,sizeof(dp)); | |
for(i=0;i<N;i++) | |
for(j=0;j<=i;j++) | |
scanf("%lld",&a[i][j]); | |
for(i=N,k=N-1;i<2*N-1;i++,k--) | |
for(j=0;j<k;j++) | |
scanf("%lld",&a[i][j]); | |
dp[0][0]=a[0][0]; | |
for(i=0;i<N-1;i++) | |
for(j=0;j<=i;j++) | |
{ | |
dp[i+1][j] = max(dp[i+1][j],a[i+1][j] + dp[i][j]); | |
dp[i+1][j+1] = max(dp[i+1][j+1],a[i+1][j+1] + dp[i][j]); | |
} | |
for(i=N,k=N-1;i<2*N-1;i++,k--) | |
for(j=0;j<k;j++) | |
{ | |
y=max(dp[i-1][j],dp[i-1][j+1]); | |
dp[i][j] = a[i][j]+y; | |
} | |
printf("Case %d: %lld\n",++kase,dp[2*N-2][0]); | |
} | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment