f314: 3. 勇者修煉 APCS 2020.10.17

 https://zerojudge.tw/ShowProblem?problemid=f314

APCS 2020.10.17

沒想到今年第三題就需要用到演算法，感覺這次的5分應該會比7月的考試更有鑑別度了。

50*10000的矩陣，每個點有三個方向，如果用DFS可能要做到海枯石爛才做得完。

仔細觀察一下，其實這題跟

https://zerojudge.tw/ShowProblem?problemid=a693

https://zerojudge.tw/ShowProblem?problemid=a694

吞食天地這兩題有87%像，如果等等程式碼看不太懂的話，建議可以先挑戰吞食天地的題組，這題我是每一行從左掃到右，從右掃到左，去找單行每個點的最佳解。(當然上走到下也要走)。

試著舉例：

第I個點的最佳解為：

max(從左走到第I-1個點+第I個點的經驗值 , 第I個點的經驗值 , 從右走到第I+1個點+第I個點的經驗值  , 從上面走到第I個點+第I個點的經驗值)。

每個點依循這原則，加上判斷一下臨界點就可以囉。

程式碼如下：

如果有問題歡迎留言或來信討論

import sys
ans=0-sys.maxsize
m,n=tuple([int(i) for i in input().split()])
MAP=[[int(j) for j in input().split()] for i in range(m)]
dp_left =[[ans for i in range(n)] for j in range(m)]
dp_right=[[ans for i in range(n)] for j in range(m)]
dp =[[ans for i in range(n)] for j in range(m)]

dp_right[0][0] = MAP[0][0]
dp_left[0][n-1] = MAP[0][n-1]
for i in range(1,n):
  dp_right[0][i] = max([dp_right[0][i-1] + MAP[0][i] , MAP[0][i]])
  dp_left[0][n-i-1] = max([dp_left[0][n-i] + MAP[0][n-i-1] , MAP[0][n-i-1]])
  dp[0][i] = max([dp_right[0][i] , dp_left[0][i]])
  dp[0][n-i-1] = max([dp_right[0][n-i-1] , dp_left[0][n-i-1]])

half = int(n/2)
for j in range(1,m):
  for i in range(0,n):
    if i == 0:
      dp_right[j][i] = dp[j-1][i]
    else:
      dp_right[j][i] = max([dp_right[j][i-1], dp[j-1][i]])
    dp_right[j][i] += MAP[j][i]

    if i == 0:
      dp_left[j][n-i-1] = dp[j-1][n-i-1]
    else:
      dp_left[j][n-i-1] = max([dp_left[j][n-i] , dp[j-1][n-i-1]])
    dp_left[j][n-i-1] += MAP[j][n-i-1]

    if i >= half:
      dp[j][i] = max([dp_right[j][i] , dp_left[j][i]])
      dp[j][n-i-1] = max([dp_right[j][n-i-1] , dp_left[j][n-i-1]])


print(max(dp[m-1]))