今天 14:25 哈尔滨理工大学 发布于黑龙江
关注
C++自存错题（12）数字三角形
观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
在上面的样例中，从 7→3→8→7→5 的路径产生了最大权值。
输入格式
第一个行一个正整数 r，表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
输出格式
单独的一行，包含那个可能得到的最大的和。
输入输出样例
输入 #1复制
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出 #1复制
30
说明/提示
【数据范围】
对于 100% 的数据，1≤r≤1000，所有输入在 [0,100] 范围内。
#include <iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
int n[1001][1001];
int main() {
int r;
cin >> r;
for (int i = 0; i < r; i++) {
for (int j = 0; j <=i; j++) {
cin >> n[i][j];
}
}
for (int i = r-2; i>=0; i--) {
for (int j =0; j<=i; j++) {
n[i][j] += max(n[i + 1][j], n[i + 1][j + 1]);
}
}
cout << n[0][0] << endl;
return 0;
}
写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
在上面的样例中，从 7→3→8→7→5 的路径产生了最大权值。
输入格式
第一个行一个正整数 r，表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
输出格式
单独的一行，包含那个可能得到的最大的和。
输入输出样例
输入 #1复制
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出 #1复制
30
说明/提示
【数据范围】
对于 100% 的数据，1≤r≤1000，所有输入在 [0,100] 范围内。
#include <iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
int n[1001][1001];
int main() {
int r;
cin >> r;
for (int i = 0; i < r; i++) {
for (int j = 0; j <=i; j++) {
cin >> n[i][j];
}
}
for (int i = r-2; i>=0; i--) {
for (int j =0; j<=i; j++) {
n[i][j] += max(n[i + 1][j], n[i + 1][j + 1]);
}
}
cout << n[0][0] << endl;
return 0;
}
全部评论
相关推荐
点赞 评论 收藏
分享
12-16 16:12
门头沟学院 前端工程师 
点赞 评论 收藏
分享
投递字节跳动等公司6个岗位 点赞 评论 收藏
分享
12-25 13:37
门头沟学院 Java sneak@0729：标准回答：我期望在广州，但我个人其实对地域选择不敏感，更看重公司的前景和个人长期发展。因此base地具体以公司安排为准
点赞 评论 收藏
分享
程序员牛肉：不用，你低估你学历的含金量了。
不用学微服务，重心放到juc，redis和mysql的八股上。然后准备两个简历项目。直接准备明年暑期就好。南京大学都算是国内比较顶尖的985了。明年暑期零实习也能被约面。不用太焦虑 点赞 评论 收藏
分享