light oj---1004 - Monkey Banana Problem

1. #include<stdio.h>
2. #include<string.h>
3. #define LL long long
4. LL dp[210][210],num[210][210],n;
6. LL max(LL a,LL b)
7.  {
8.      if(a>b) return a;
9.      return b;
10.  }
12. LL call(LL a,LL b)
13.  {
14.      if(num[a][b]==0) return 0;
16.      if(dp[a][b]!=-1) return dp[a][b];
19.      LL ret=num[a][b];
20.      if(a<=n)
21.       ret+=max(call(a-1,b),call(a-1,b-1));
22.      else
23.      ret+=max(call(a-1,b),call(a-1,b+1));
25.      return dp[a][b]=ret;
26.  }
28. int main()
29.  {
30.      int t;
31.      scanf("%d",&t);
33.      for(int i=1;i<=t;i++)
34.       {
36.           scanf("%lld",&n);
37.           for(int j=0;j<=200;j++)
38.             for(int k=0;k<=200;k++)
39.               {
40.                    num[j][k]=0;
41.                    dp[j][k]=-1;
42.               }
43.           for(int j=1;j<n;j++)
44.            for(int k=1;k<=j;k++)
45.              scanf("%lld",&num[j][k]);
46.           for(int j=n;j<2*n;j++)
47.            for(int k=1;k<=2*n-j;k++)
48.              scanf("%lld",&num[j][k]);
51.           LL ans=num[2*n-1][1];
52.           ans+=max(call(2*n-2,1),call(2*n-2,2));
53.           printf("Case %d: %lld\n",i,ans);
56.       }
57.       return 0;
58.  }