f314 - 3. 勇者修煉
題目描述
題目給定一個 $m \times n$ 的矩陣，每個格子代表一個經驗值。勇者可以從第一排的任意位置開始，到最後一排的任意位置結束。每次移動可以往左、往右或往下走，但不能重複經過同一個格子。目標是找到一條路徑，使得獲得的經驗值總和最大。
解題思路
本題可以使用動態規劃來解決。定義 ans[i] 為到達第 i 列的最大經驗值。對於每一列，我們可以從上一列的每個位置到達當前列的每個位置。
b[i] 表示從第一列到第 i 列的最大經驗值，只考慮從左邊過來的路徑。
c[i] 表示從最後一列到第 i 列的最大經驗值，只考慮從右邊過來的路徑。
ans[i] 為 b[i] 和 c[i] 的最大值，表示到達第 i 列的最大經驗值。
最終答案為所有 ans[i] 的最大值。
複雜度分析
- 時間複雜度: O(m * n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
long long int m,n,a[10001],b[10001],c[10001],ans[10001],score=-1000000,tmp;
int main(){
cin >> m >> n;
while(m--){
for(int i=0;i<n;++i){
cin >> a[i];
b[i]=0;
c[i]=0;
}
b[0]=ans[0]+a[0];
for(int i=1;i<n;++i){
b[i]=max(ans[i]+a[i],b[i-1]+a[i]);
}
c[n-1]=ans[n-1]+a[n-1];
for(int i=n-2;i>=0;--i){
c[i]=max(ans[i]+a[i],c[i+1]+a[i]);
}
for(int i=0;i<n;++i){
ans[i]=max(b[i],c[i]);
}
}
for(int i=0;i<n;++i){
score=max(score,ans[i]);
}
cout << score;
}