没什么好说的，这是我学DP的第一道题目。

 

1 //#define LOCAL 2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7  8 int a[103][103]; 9 10 int main(void)11 {12     #ifdef LOCAL13         freopen("2084in.txt", "r", stdin);14     #endif15 16     int C;17     scanf("%d", &C);18     while(C--)19     {20         int n;21         scanf("%d", &n);22         int i, j;23         for(i = 1; i <= n; ++i)24             for(j = 1; j <= i; ++j)25                 scanf("%d", &a[i][j]);26 27         for(i = n-1; i >= 1; --i)28             for(j = 1; j <= i; ++j)29                 a[i][j] += max(a[i+1][j], a[i+1][j+1]);30 31         printf("%d\n", a[1][1]);32     }33     return 0;34 }