51Nod一級演算法1002數塔取數問題

---恢復內容開始---

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #define max(x,y) ((x)>(y)?(x):(y))
 4 int main(){
 5     int n;
 6     int i,j,k;
 7     scanf("%d",&n);//層數
 8     k = (n+1)*n/2;//所有節點總數
 9     int *a = (int*) malloc(sizeof(int) * k);//動態數組，記錄每個節點的數
10     for(i = 0; i < k; i++){//輸入各個節點數
11         scanf("%d",&a[i]);
12     }
13     k -= n;//倒數第二層的第一個節點
14     for(i = k-1, j = 0; i>= 0 ; i--){
15         a[i] = a[i] + max(a[i+n],a[i+n-1]);//貪心，將下層的左or右節點的最大值加到自身
16         if(++j == n-1){//遍歷完一層就n-1
17             n--;
18             j = 0;
19         }
20     }
21     printf("%d\n",a[0]);
22     return 0;
23 }

思路：從倒數第二行開始，每個節點的值加上它下一層的左右節點的最大值，然後逐層向上遍歷，直到頂點，迴圈結束，輸出頂點內容

---恢復內容結束---