[USACO1.5][IOI1994]数字三角形 Number Triangles

题目描述

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

        7 3   8 8   1   0 2   7   4   4 
4   5   2   6   5 

在上面的样例中,从 $7\to 3\to 8\to 7\to 5$ 的路径产生了最大

输入格式

第一个行一个正整数 $r$ ,表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

输出格式

单独的一行,包含那个可能得到的最大的和。

样例 #1

样例输入 #1

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

样例输出 #1

30

提示

【数据范围】
对于 $100\%$ 的数据，$1\le r\le 1000$，所有输入在 $[0,100]$ 范围内。

题目翻译来自NOCOW。

USACO Training Section 1.5

IOI1994 Day1T1

所需变量

int r;//代表行数

int arr[1005][1005];//用于接收每行每个数

int L[2][1005] = {0};//每行不断交替存储其最大值
int i,j;//循环变量

思路：因为我们要找到最大值的一条路，我们不妨不断从下面往上判断，每次将最大值都存储起来，然后不断累加上去得到得到最大值！
首先就是将最底下那行前部赋值给L数组，因为最底下那行我们也不知道谁可能会被排除！

for(i = r-1;i>=0;--i){L[(r-1)%2][i] = arr[r-1][i];}

得到当前的最大值行后就是往上一行判断，看目前这个数是加上左下那个数更大还是右下那个数更大，将加上后的数判断，将更大的那个数赋值给当前的L数组的另外一行！

for(i = r-2;i>=0;--i){for(j = 0;j<=i;++j){L[i%2][j] = arr[i][j];L[i%2][j] += L[(i+1)%2][j]>L[(i+1)%2][j+1]?L[(i+1)%2][j]:L[(i+1)%2][j+1];}}

不断迭代下去我们最上面那个数就是我们要求的最大值！也就是我们找到最大值！
该算法本人认为比较优，如果有更好的想法，欢迎q我！
完整代码如下（编译器是dev，语言是C语言）：

#include<iostream>
using namespace std;
int main(){int r,arr[1005][1005],L[2][1005] = {0},temp,i,j;cin>>r;for(i = 0;i<r;i++){for(j = 0;j<=i;j++){cin>>arr[i][j];}}for(i = r-1;i>=0;--i){L[(r-1)%2][i] = arr[r-1][i];}for(i = r-2;i>=0;--i){for(j = 0;j<=i;++j){L[i%2][j] = arr[i][j];L[i%2][j] += L[(i+1)%2][j]>L[(i+1)%2][j+1]?L[(i+1)%2][j]:L[(i+1)%2][j+1];}}cout<<L[0][0]<<endl;return 0;}

旅游攻略