数塔问题
| 试题描述 |
|
如图所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径,使该路径所经过的数字总和最大。只要求输出总和。 1. 一步可沿左斜线向下或右斜线向下走; 2. 三角形行数小于等于100; 3. 三角形中的数字为0,1,…,99; 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
|
| 输入 |
| 输入数据共n+1行,第一行为三角形行数n,后面n行表三角形每一行的数字。 |
| 输出 |
| 输出结果总和。 |
| 输入示例 |
| 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 |
| 输出示例 |
| 30 |
#includeusing namespace std; int main() { int a[101][101],n,sum=0; cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) cin>>a[i][j]; for(int i=n-1;i>=1;i--) { for(int j=i;j>=1;j--) { if(a[i+1][j+1]>=a[i+1][j]) a[i][j]+=a[i+1][j+1]; else a[i][j]+=a[i+1][j]; } } cout<1][1]; }