P1216 数字三角形*
【题目来源】
洛谷：P1216 [IOI 1994] 数字三角形 Number Triangles - 洛谷
【题目描述】
观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
在上面的样例中，7→3→8→7→5 的路径产生了最大权值。
【输入】
第一个行一个正整数 r ,表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
【输出】
单独的一行,包含那个可能得到的最大的和。
【输入样例】
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
【输出样例】
30
【解题思路】
【算法标签】
《洛谷 P1216 数字三角形》 #动态规划,dp# #递推# #USACO# #IOI# #2001#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
int r, sum=0, mark;
int a[1005][1005]={0};
int main()
{cin >> r; // 输入rfor (int i=1; i<=r; i++) { // 使用二维数组记录输入的数字for (int j=1; j<=i; j++) { // 每列长度不一样，注意这里是j<=icin >> a[i][j];}}for (int i=r-1; i>=1; i--) { // 使用线性dp方法，从倒数第二行开始计算for (int j=1; j<=i; j++) { a[i][j] = max(a[i][j]+a[i+1][j], a[i][j]+a[i+1][j+1]); // 每个元素修改为与左下方相加或与右下角相加的最大值}}cout << a[1][1] << endl; // 最后输出顶端位置的值return 0;
}
【运行结果】
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
30