題目描述

觀察下面的數字金字塔。

寫一個程序來查找從最高點到底部任意處結束的路徑，使路徑經過數字的和最大。每一步可以走到左下方的點也可以到達右下方的點。

在上面的樣例中，從 $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

常規的最大路徑和，考慮dp做法。
dp[i][j] 為到達第 i 行第 j 個點的最大路徑。
轉移方程：$dp[i][j]=max(dp[i?1][j?1],dp[i?1][j])+dp[i][j]$

#include<bits/stdc++.h>
using namespace std;int main(){int r;cin >> r; vector<vector<int>> a(r + 1, vector<int>(r + 1));for (int i = 1; i <= r; ++i) {for (int j = 1; j <= i; ++j) {cin >> a[i][j];}}const int INF = -1000000000;vector<vector<int>> dp(r + 1, vector<int>(r + 1, INF));dp[1][1] = a[1][1];for (int i = 2; i <= r; ++i) {for (int j = 1; j <= i; ++j) {int best_prev = INF;if (j > 1) {best_prev = max(best_prev, dp[i-1][j-1]);}best_prev = max(best_prev, dp[i-1][j]);dp[i][j] = best_prev + a[i][j];}}int ans = INF;for (int j = 1; j <= r; ++j) {ans = max(ans, dp[r][j]);}cout << ans;return 0;
}