hdu 2084

#include<stdio.h> 

 int a[122][122]; 

 int main() 

 { 

     int c; 

     int n; 

     int i,j; 

     scanf("%d",&c); 

     while(c--) 

     { 

         scanf("%d",&n); 

         for(i=1;i<=n;i++) 

             for(j=1;j<=i;j++) 

                 scanf("%d",&a[i][j]); 

         for(i=n;i>=2;i--) 

             for(j=1;j<i;j++) 

             { 

                 if(a[i][j]>a[i][j+1]) 

                     a[i-1][j]+=a[i][j]; 

                 else 

                     a[i-1][j]+=a[i][j+1]; 

             } 

         printf("%d\n",a[1][1]); 

     } 

     return 0; 
}
状态转移方程a[i][j]=a[i][j]+max(a[i+1][j],a[i+1][j+1]);