【題解】Zerojudge f314 - 3. 勇者修煉

題目連結

題目大意

給定一張

$n \times m$ 的地圖，每個位置有分數

$a[i][j]$ ，經過就可以加分。你可以從第

$1$ 行的任意位置出發，第

$n$ 行的任意位置結束，過程中只能往左、往右、或往下走，且不能走回經過的位置。問最高能獲得多少分？

$1 \leq n \leq 50$
$1 \leq m \leq 10000$

題解

定義

$dp[i][j]$ 為走到第

$i$ 行第

$j$ 列的最高分數。對於第

$i$ 行，我們假設他先停在第

$i - 1$ 行的某個位置

$(i - 1, k)$ ，然後往下走到

$(i, k)$ ，最後再透過左右移動走到

$(i, j)$ 。假設最後選擇往右移動，不難發現

$dp[i][j] = \max\limits_{k \leq j} dp[i - 1][k] + \sum\limits_{p = k}^j a[i][p]$ ，這一串算式可以透過類似前綴和的方式預處理。往左走的情況也是類似。最後

$dp[i][j]$ 就是取往左或往右的最大值。實作細節請參考 code。

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<vector<int>> a(n, vector<int>(m));
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	vector<int> dp(m);
	for(int i = 0; i < n; i++) {
		vector<int> pref(m);
		pref[0] = dp[0] + a[i][0];
		for(int j = 1; j < m; j++) {
			pref[j] = max(pref[j - 1], dp[j]) + a[i][j];
		}
		vector<int> suff(m);
		suff[m - 1] = dp[m - 1] + a[i][m - 1];
		for(int j = m - 2; j >= 0; j--) {
			suff[j] = max(suff[j + 1], dp[j]) + a[i][j];
		}
		for(int j = 0; j < m; j++) {
			dp[j] = max(pref[j], suff[j]);
		}
	}
	cout << *max_element(dp.begin(), dp.end()) << "\n";
	return 0;
}