洛谷p1216 IOI1994 Day1T1

题目描述

观察下面的数字金字塔。

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

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： 

573 88 1 02 7 4 44 5 2 6 5

输出样例#1： 

30

说明

题目翻译来自NOCOW。

USACO Training Section 1.5

IOI1994 Day1T1

---

解

---

正着的递推

先用从下到上的算法

1 //洛谷p1216  2 #include
     
       3 using namespace std; 4 int max(int a,int b){
   return a>b?a:b;} 5 int main(){ 6 int r; 7 cin>>r; 8 int triangle[r][r]; 9 for(int i=0;i
      
       >triangle[i][j];12 13 for(int i=r-2;i>=0;i--)14 for(int j=r-2;j>=0;j--)15 triangle[i][j]+=max(triangle[i+1][j],triangle[i+1][j+1]); 16 cout<
      
     

看！代码是如此的简洁，结构是如此的清晰！

算法讲解

行8~11：输入三角形。

由于三角形一行的个数是行行递增的，

所以

10 for(int j=0;j

  可以使得每行的j的最大值与行号相等。

行13~16：递归计算

从倒数第二行的最后一个数开始，把每一个数（[i][j]）都加上（+=）它下面的数（[i+1][j]），右下角的数（[i+1][j+1]）中的最大值（max(a,b)）.

这里有一个我开始犯的错误：

13 for(int i=r-2;i>=0;i--)14 for(int j=r-2;j>=0;j--)15 triangle[i][j]+=max(triangle[i+1][j],triangle[i+1][j+1]); 16 cout<

为什么这里是r-2呢？（之前我就在这里被坑了，本地测试数据答案超大.....）

理解一下：

首先，r是三角形的长宽

又∵第一行第一列是（0,0）

∴最后一行最后一列是（r-1，r-1）

又∵我们是从倒数第二行的最后一个数开始回归的

∴这个数为（r-2，r-2）

最后，行16：输出在首行首列的结果

完毕！

---

倒着的递推

再用从上到下的算法

（未完待续。。。）