You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

#include <iostream>
using namespace std;
const int N = 1e3 + 9;
const int inf = 1000000000;
int f[N][N];
int main() {


	return 0;
}

阿Q在玩一款游戏，他在一个山顶，现在他要下山，山上有许多水果，阿Q每下一个高度就可以捡起一个水果，并且获得水果的能量。山的形状如图所示：

   3
  1 2
 6 2 3
3 5 4 1

这是一个高度为 4 的山，数字代表水果的能量。每次下一个高度，阿Q需要选择是往左下走，还是往右下走。例如：对于上图的情况，阿Q能获得的最大能量为，3 + 1 + 6 + 5 = 15。现在，阿Q希望你能帮他计算出下山能获得的最大能量。

这里我们依然是先寻找状态转移方程（递推式），我们发现

f[i][j]=f[i][j]+max(f[i−1][j],f[i−1][j−1])

所以我们接下来，根据状态转移方程实现代码就可以了。

我们先接收数据。

请在main函数中写下：

int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
  	for (int j = 1; j <= i; ++j) {
    	cin >> f[i][j];
  	}
}

这里我们定义ma表示最后的答案，并给了一个初始值--负无穷。

请在return 0;上面写下：

int ma = -inf;

接下来我们就可以写我们的递推式了。

请在return 0;上面写下：

for (int i = 1; i <= n; ++i) {
  	for (int j = 1; j <= i; ++j) {
    	f[i][j] += max(f[i - 1][j], f[i - 1][j - 1]);
  	}
}

这里如果是你自己写的时候要注意好边界问题，我们这里下标从 1 开始有两个原因：

1：这里不会出现访问越界的问题（访问到我们没有定义的空间）。

2：访问的其他的数据是零（例如：f[0][0] = 0），所以不会影响答案。

我们知道最后的答案，就在最后一行。所以我们可以在最后一行找到最大值就可以了。

请在f[i][j] += max(f[i - 1][j], f[i - 1][j - 1]);下面写下：

if (i == n) {
  	ma = max(f[i][j], ma);
}

这里我们也有一个要注意的地方。我们需要判断是否是最后一行。

其实这道题目是可以不用判断最后一行的，因为所有的数字都是正的。但如果里面有负值的话，那么直接取最大值的方法就可能是不对的。

这个时候我们发现我们已经得到了最后的答案，所以我们就可以输出最后的答案了。

需要注意，如果当前算出的ma的结果为-inf，说明n的值为 0，需要将ma的结果改为 0。

请在return 0;上面写下：

if (ma == -inf) {
    ma = 0;
}
cout << ma << endl;

现在你可运行你的程序了。看看阿Q下山可以获取的最大能量了。

赶快输入下面数据测试吧。

4
3
1 2
6 2 3
3 5 4 1

思考：

不知道聪明的同学有没有想过，我们正着写代码，最后的答案是出现在最后一行。但是最后一行有太多的数字。所以我们是不是可以反着想，如果我们写一个倒着的状态转移方程。那么最后的答案不就是山顶元素？

不知道这个时候聪明的你是否已经理解了，赶快亲自动手实现一个倒着写的代码吧。

这里我想给大家说的是，动态规划就是这样。思考问题不要只是惯性思维思考（正着思考问题），有时候我们倒着写会比正着好许多。希望大家通过这个题目可以把思维打开，多角度思考问题。