P1216 [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 57→3→8→7→5 的路径产生了最大

输入格式

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

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

输出格式

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

输入输出样例

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

30

说明/提示

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

题目翻译来自NOCOW。

USACO Training Section 1.5

IOI1994 Day1T1

 1 #include<bits/stdc++.h>
 2 #define MAX 1005
 3 using namespace std;
 4 int D[MAX][MAX];
 5 int maxSum[MAX][MAX];
 6 int n;
 7 int MaxSum(int i,int j){ //i为行数，j为列数，即每行第几个元素 
 8     if(maxSum[i][j]!=-1)
 9         return maxSum[i][j];
10     if(i==n) //当递进到第n行开始回归，进行到最后一行时，只返回最底层的那个值 
11         maxSum[i][j] = D[i][j];
12     else{
13         int x=MaxSum(i+1,j); //正下方的元素 
14         int y=MaxSum(i+1,j+1); //右下方的元素 
15         //没进行到最后一行时，让正下方和右下方的元素对比，取最大值加给本元素 
16         maxSum[i][j]=D[i][j]+max(x,y); //注意，这里的max不是MaxSum 
17     }
18     return maxSum[i][j];
19 }
20 int main(){
21     int i,j;
22     cin>>n; //输入，将输入写入数组D 
23     for(int i=1;i<=n;i++)
24         for(int j=1;j<=i;j++){
25             cin>>D[i][j];
26             maxSum[i][j]=-1;
27         }            
28     cout<<MaxSum(1,1)<<endl;
29 }