1258:【例9.2】数字金字塔 2021-01-15

简介: 1258:【例9.2】数字金字塔 2021-01-15

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. }

 

相关文章
|
监控 算法 安全
基于伽马变换自适应修正的全景首尾融合算法
基于伽马变换自适应修正的全景首尾融合算法
106 0
线代的几何意义(一)——向量,坐标,矩阵
线代的几何意义(一)——向量,坐标,矩阵
|
9月前
|
算法 Java 计算机视觉
基于像素的皮肤检测技术
基于像素的皮肤检测技术
47 1
|
9月前
拉普拉斯金字塔
【6月更文挑战第4天】拉普拉斯金字塔。
45 1
|
10月前
数字组合 (计蒜客 - T1218)
数字组合 (计蒜客 - T1218)
|
编解码
编码生成矩阵与检错监督矩阵
编码生成矩阵与检错监督矩阵
277 0
编码生成矩阵与检错监督矩阵
|
自动驾驶 计算机视觉
使用扩张卷积的语义分割
使用扩张卷积训练语义分割网络。语义分割网络对图像中的每个像素进行分类,从而生成按类分割的图像。语义分割的应用包括自动驾驶的道路分割和医疗诊断的癌细胞分割。
102 0
|
算法 计算机视觉
基于小波变换编码的纹理图像分割
基于小波变换编码的纹理图像分割
184 0
基于小波变换编码的纹理图像分割