# 演算法題 - 勇者修煉 - APCS - by Peter Wang
## 題目資訊
此題為2020.10 測驗中的題目3
###### tags: `APCS` `DP`

## 題目敘述
給定 *m×n* 大小的的陣列，每一格是一個介於 -100 與 100 之間的整數，表示經過這格可以累積的經驗值。
你可以從最上面一排任何一個位置開始，在最下面一排任何一個位置結束。
過程中每一步可以選擇往左、往右或往下走，但不能走回已經經過的位置。
請你算出最多可以獲得的經驗值總和(可能是負數)。

### 輸入：
第一行有兩個正整數 *m,n*(1≤m≤50,1≤n≤10000)
接下來 m 行，每行包含 n 個整數。第 *i* 行的第 *j* 個數字表示在 (i,j) 位置可以得到的經驗值。

### 輸出：
輸出可以獲得的最多經驗值總和。

## 解題思路
此題叫一般DP更為複雜，必須分為左DP及又DP，簡單說就是從左邊做一次找對大直DP，同時也做一次從右邊來的DP，最後比較兩種DP取最大值。

## 程式碼

#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
long long dpr[52][10002];
long long dpl[52][10002];
int main(){
    int m,n;
    while(cin>>m){
        cin>>n;
        long long arr[52][10002];
        memset(arr,0,sizeof(arr));
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                cin>>arr[i][j];
                dpr[i][j]=arr[i][j];
                dpl[i][j]=arr[i][j];
            }
        }
        int x=0;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dpr[i][j]+=max(max(dpr[i-1][j],dpl[i-1][j]),dpr[i][j-1]);
            }
            for(int j=n;j>=1;j--){
                dpl[i][j]+=max(max(dpr[i-1][j],dpl[i-1][j]),dpl[i][j+1]);
            }
        }
        int maxn=0;
        for(int i=1;i<=n;i++){
            int num=max(dpl[m][i],dpr[m][i]);
            if(num>maxn){
                maxn=num;
            }
            else{
                continue;
            }
        }
        cout<<maxn<<endl;
    }
}

## 資料來源
[Zerojudge](https://zerojudge.tw/)
[題目敘述](https://zerojudge.tw/ShowProblem?problemid=f314)

## 備註
>[name=PeterWang]
>[time=Sun, Jun 13, 2021 9:59 AM]