hdu2084 参考答案

   1 #include <iostream>
   2 using namespace std;
   3 const int N=110;
   4 int a[N][N];
   5 int f[N][N];
   6 int n;
   7 void Init()
   8 {
   9         scanf("%d",&n);
  10         for(int i=0;i<n;i++)
  11                 for(int j=0;j<=i;j++)
  12                         scanf("%d",&a[i][j]);
  13         memset(f,-1,sizeof(f));
  14 }
  15 int DP(int i,int j)
  16 {
  17         int ans;
  18         if(f[i][j]>=0)
  19                         return f[i][j];
  20         if(i==n-1)
  21                 ans=a[i][j];
  22         else
  23         {
  24                 if(DP(i+1,j)>DP(i+1,j+1))
  25                         ans=a[i][j]+DP(i+1,j);
  26                 else
  27                         ans=a[i][j]+DP(i+1,j+1);                
  28         }
  29         f[i][j]=ans;
  30         return f[i][j];
  31 }
  32 int main()
  33 {
  34         int test;
  35         cin>>test;
  36         while(test-->0)
  37         {
  38                 Init();
  39                 printf("%d\n",DP(0,0));
  40         }
  41 }