51nod:1002 数塔取数问题

51nod:1002 数塔取数问题

一个高度为N的由正整数组成的三角形，从上走到下，求经过的数字和的最大值。

每次只能走到下一层相邻的数上，例如从第3层的6向下走，只能走到第4层的2或9上。

5

8 4

3 6 9

7 2 9 5

例子中的最优方案是：5 + 8 + 6 + 9 = 28

Input

第1行：N，N为数塔的高度。(2 <= N <= 500) 第2 - N + 1行：每行包括1层数塔的数字，第2行1个数，第3行2个数......第k+1行k个数。数与数之间用空格分隔（0 <= A[i] <= 10^5) 。

Output

输出最大值

Input示例

4 5 8 4 3 6 9 7 2 9 5

Output示例

28

显然，数塔的高度<=500，使用深搜一定会超时，那么我们就要换一种思路求解这道题目了。

从下往上推出答案，对次一层的每个数来说，可以加上它下一层相邻两个数的最大值来更新本身，这样更新到第一层的时候也就是最终的答案。

AC代码：

#includeusing namespace std;__int64 a[505][505];int main(){ int n; cin>>n; for(int i=0; i>a[i][j]; for(int i=n-2; i>=0; i--) for(int j=0; j<=i; j++) a[i][j]+=max(a[i+1][j],a[i+1][j+1]); cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。