LightOJ - 1004 - Monkey Banana Problem

1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم   #####******************
2. __________________________________________________________________________
3. ######################  Ya-Seen Arafat(ACWizard) #########################
4. ######################        UAP-CSE-33B        #########################
5. *************************************************************************/
6. #include <bits/stdc++.h>
7. #define sc(n) scanf("%d", &n)
8. #define scD(n) scanf("%lf", &n)
9. #define scS(n) scanf("%s", &n)
10. #define S 103
11. using namespace std;
13. int n, ar[S*3][S];
14. int dp[S*3][S], sz[S*3];
16. int MB(int row, int ind, int jump){
17.     if(row > (n+n-1) || ind < 0 || ind > sz[jump])return 0;
18.     if(dp[jump][ind] != -1)return dp[jump][ind];
19.     if(row < n)dp[jump][ind] = (ar[jump][ind] + max(MB(row+1, ind, jump+1), MB(row+1, ind+1, jump+1)));
20.     else dp[jump][ind] = (ar[jump][ind] + max(MB(row+1, ind-1, jump+1), MB(row+1, ind, jump+1)));
21.     return dp[jump][ind];
22. }
24. int main(){
25.     int t, cs = 0;
26.     scanf("%d", &t);
27.     while(t--){
28.         memset(dp, -1, sizeof(dp));
29.         memset(ar, 0, sizeof(ar));
30.         scanf("%d", &n);
31.         int z;
32.         for(int i = 0; i < n; i++){
33.             for(int j = 0; j <= i; j++){
34.                 scanf("%d", &ar[i][j]);
35.             }
36.             sz[i] = i;
37.             z = i;
38.         }
39.         int jj = n-1;
40.         for(int i = z+1; i < (n+n-1); i++){
41.             for(int j = 0; j < jj; j++){
42.                 scanf("%d", &ar[i][j]);
43.             }
44.             sz[i] = jj-1;
45.             jj--;
46.         }
47.         int ans = MB(1, 0, 0);
48.         cout << "Case " << ++cs << ": " << ans << endl;
49.     }
50.     return 0;
51. }