数塔（杭电oj2084）

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath> 
 5 using namespace std;
 6 
 7 int main() {
 8     int num[105][105];
 9     int number[105];
10     int T;
11     cin >> T;
12     while(T--) {
13         int N;
14         cin >> N;
15         //读入数据 
16         for(int i = 0; i < N; i++) {
17             for(int j = 0; j < i + 1; j++) {
18                 cin >> num[i][j];
19             }
20         }
21         //用来存储遍历每一行之后的结果 
22         memset(number, 0, sizeof(number));
23         //初始化，将最后一行的值赋值给number数组 
24         for(int i = 0; i < N; i++) {
25             number[i] = num[N-1][i];
26         }
27         //从下向上遍历数组， 更新数组number， 每次用下一行相邻的俩个数的最大值加上上一行的数更新number， 最后number[0]即为所求 
28         for(int i = N - 2; i >= 0; i--) {
29             for(int j = 0; j < i + 1; j++) {
30                 number[j] = num[i][j] + max(number[j], number[j+1]);
31             }
32         }
33         cout << number[0] << "\n";
34     }
35 }