1258：【例9.2】数字金字塔
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
观察下面的数字金字塔。写一个程序查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以从当前点走到左下方的点也可以到达右下方的点。
在上面的样例中,从13到8到26到15到24的路径产生了最大的和86。
【输入】
第一个行包含R(1≤ R≤1000)，表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
所有的被供应的整数是非负的且不大于100。
【输出】
单独的一行，包含那个可能得到的最大的和。
【输入样例】
5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
【输出样例】
86
1. #include <stdlib.h> 2. #include <cstdio> 3. #include <algorithm> 4. #include <iostream> 5. using namespace std; 6. const int M=1005; 7. int a[M][M][4],n; 8. int main() 9. { 10. scanf("%d",&n); 11. for(int i=1;i<=n;i++) 12. for(int j=1;j<=i;j++){ 13. scanf("%d",&a[i][j][1]);//原数 14. a[i][j][2]=a[i][j][1];//存储最大值 15. a[i][j][3]=0;//记录路径 0下 1右 16. } 17. for(int i=n-1;i>=1;i--) 18. for(int j=1;j<=i;j++){ 19. if(a[i+1][j][2]>a[i+1][j+1][2]){ 20. a[i][j][2]=a[i][j][2]+a[i+1][j][2]; 21. a[i][j][3]=0; 22. } 23. else{ 24. a[i][j][2]=a[i][j][2]+a[i+1][j+1][2]; 25. a[i][j][3]=1; 26. } 27. } 28. printf("%d\n",a[1][1][2]); 29. //int y=1;//输出最优路径 30. //for(int i=1;i<n;i++){ 31. // printf("%d->",a[i][y][1]); 32. // y+=a[i][y][3]; 33. //} 34. //printf("%d\n",a[n][y][1]); 35. //system("pause"); 36. return 0; 37. }
