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. OK, I Understand
 
Top