【題解】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;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge f314 - 3. 勇者修煉