首页 > 代码库 > The Triangle
The Triangle
针对如下形式的ACM试题,大多出自南阳理工学院的在线ACM试题(网址: 南阳理工在线评测系统),在此非常感谢,同时也非常感谢作者的分享!
时间限制:1000 ms | 内存限制:65535 KB
难度:4
- 描述
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
(Figure 1)
Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.
- 输入
- Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.
- 输出
- Your program is to write to standard output. The highest sum is written as an integer.
- 样例输入
573 88 1 0 2 7 4 44 5 2 6 5
- 样例输出 30
1 #include <stdio.h> 2 #include<string.h> 3 int max(int a, int b){ 4 return (a>b)?a:b; 5 } 6 7 int main() 8 { 9 int n;10 int arr[100][100];11 int sumdpth[100][100];12 scanf("%d", &n);13 int tmpmax = 0;14 for (int i = 0; i < n; ++i) {15 for (int j = 0; j < i+1; ++j) {16 arr[i][j] = sumdpth[i][j] = 0;17 scanf("%d", &arr[i][j]);18 sumdpth[i][j] = arr[i][j];19 }20 }21 22 for (int i = 1; i < n; ++i) {23 for (int j = 0; j < i+1; ++j) {24 if(j == 0){25 sumdpth[i][j] = arr[i-1][j];26 }27 sumdpth[i][j] = max(sumdpth[i-1][j]+arr[i][j],sumdpth[i-1][j-1]+arr[i][j]) ;28 if(tmpmax < sumdpth[i][j]) tmpmax = sumdpth[i][j];29 }30 }31 32 printf("%d\n", tmpmax);33 /*34 for (int i = 0; i < n; ++i) {35 for (int j = 0; j < i+1; ++j) {36 printf("%d ", arr[i][j]);37 }38 printf("\n");39 }40 */41 42 }
The Triangle
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。