題目描述

觀察下面的數字金字塔。

寫一個程序來查找從最高點到底部任意處結束的路徑，使路徑經過數字的和最大。每一步可以走到左下方的點也可以到達右下方的點。

     7 3   8 
8   1   0 

2 7 4 4
4 5 2 6 5
在上面的樣例中,從7 到 3 到 8 到 7 到 5 的路徑產生了最大

輸入輸出格式

輸入格式：
第一個行包含 R(1<= R<=1000) ,表示行的數目。

后面每行為這個數字金字塔特定行包含的整數。

所有的被供應的整數是非負的且不大于100。

輸出格式：
單獨的一行,包含那個可能得到的最大的和。

輸入輸出樣例

輸入樣例#1： 復制
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
輸出樣例#1： 復制
30
說明

題目翻譯來自NOCOW。

USACO Training Section 1.5

#include<bits/stdc++.h>
using namespace std;
int r,a[1005][1005];
int main(){scanf("%d",&r);for(int i=1;i<=r;i++)for(int j=1;j<=i;j++)scanf("%d",&a[i][j]);for(int i=r-1;i>=1;i--)for(int j=i;j>=1;j--){a[i][j]=a[i][j]+max(a[i+1][j],a[i+1][j+1]);}printf("%d",a[1][1]);
}

轉載于:https://www.cnblogs.com/sdfzsyq/p/9677252.html

總結

以上是生活随笔為你收集整理的洛谷1216 数字三角形的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。