• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# 1004 monkey banana

a guest Feb 12th, 2013 199 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include<iostream>
2. #include<cstring>
3. #include<cstdio>
4.
5. #define MAX 220
6. #define MAXI 110
7. #define inf 999
8. #define mem(x,y) memset(x,y,sizeof(x))
9. #define scan scanf("%lld",&mat[i][j]);
10. #define sn(n) scanf("%lld",&n);
11. #define pf(n) printf("Case %lld: %lld\n",cased,n);
12. #define ull  long long
13. using namespace std;
14. ull mat[MAX][MAXI],n,r,c,cased=1,test;
15. ull dp[MAX][MAXI];
16. ull call(ull i,ull j)
17. {
18.     if(i>=0 && i<r and j>=0 and j<c) //if still inside the array
19.     {
20.         if(dp[i][j]!=-1) return dp[i][j];
21.         //if(mat[i][j]==-1) return 0;
22.         //ull ret=-10;
23.         ull ret =-100;
24.                 //try to move to 3 direction,also add current cell's poull
25.
26.         ret=max(ret,call(i+1,j)+mat[i][j]);
27.         ret=max(ret,call(i+1,j-1)+mat[i][j]);
28.         ret=max(ret,call(i+1,j+1)+mat[i][j]);
29.         return dp[i][j]=ret;
30.     }
31.     else return 0; //if outside the array
32. }
33.
34.
35.
36. int main()
37. {//cout<<-inf;
38.
39.     sn(test)
40.     while(test--){
41.    sn(n)
42.     mem(dp,-1);
43.     mem(mat,-1);
44.
45.     for(ull i = 0;i<2*n-1;i++)
46.     {
47.         if(i<n)
48.         for(ull j = 0;j<=i;j++)
49.         scan
50.
51.         else
52.         for(ull j=0;j<2*n-1-i;j++)
53.         scan
54.
55.     }
56.    // cout<<mat[0][0];
57.     r = 2*n-1;
58.     c = n;
59.     //dp[0][0] = mat[0][0];
60.     pf(call(0,0));
61.     cased++;
62.     }
63.
64. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top