51Nod一级算法1002数塔取数问题

2017-11-10 07:00:57来源:cnblogs.com作者:一梦一杯酒人点击

分享

---恢复内容开始---

 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-117             n--;18             j = 0;19         }20     }21     printf("%d/n",a[0]);22     return 0;23 }

思路:从倒数第二行开始,每个节点的值加上它下一层的左右节点的最大值,然后逐层向上遍历,直到顶点,循环结束,输出顶点内容

---恢复内容结束---

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台