APCS 109/10 實作題第三題題解

2020-10-21 18:39:13 by Akira

題目敘述

有一個矩陣每一格有個 \([-100, 100]\) 間的數字，你要從最上面一列的任一格走到最下面一列的任一格，每步可以往下或左或右，走過的格子不能重複走到，問所有經過格子的數字總和最大可以多大(這個值也可能為零或負數)。

輸入格式

第一行有兩個整數 \(M, N\)
接下來有 \(M\) 行每行 \(N\) 個整數代表該矩陣

\(1 \le M \le 50, 1 \le N \le 10000\)

輸出格式

印出答案一個數字

範例輸入

2 3
5 6 7
-1 1 -100

範例輸出

子任務

20% : \(M = 1, N \le 100\)
30% : \(N \le 100\)
50% : 無限制

題解

\(O(MN)\) 動態規劃

影片

C++ 參考解答

#include <climits>
#include <algorithm>
#include <iostream>
using namespace std;

int A[52][10000];
int B[52][10000]; // B[i][j] = 到 (i,j) 能有的最大總和 (不包含A[i][j])

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
  int M, N;
  cin >> M >> N;
  for (int i = 1; i <= M; i++) {
    for (int j = 0; j < N; j++) {
      cin >> A[i][j];
    }
  }
  for (int i = 0; i <= M; i++) { // from row i to row i+1
    for (int j = 0; j < N; j++) {
      B[i + 1][j] = INT_MIN;
    }
    int maxsum = INT_MIN;
    for (int j = 0; j < N; j++) {
      maxsum = max(maxsum, B[i][j]) + A[i][j];
      B[i + 1][j] = max(B[i + 1][j], maxsum);
    }
    maxsum = INT_MIN;
    for (int j = N; --j >= 0; ) {
      maxsum = max(maxsum, B[i][j]) + A[i][j];
      B[i + 1][j] = max(B[i + 1][j], maxsum);
    }
  }
  int ans = INT_MIN;
  for (int j = 0; j < N; j++) {
    ans = max(ans, B[M + 1][j]);
  }
  cout << ans << endl;
  return 0;
}

[題解] [APCS] [APCS 109/10]

APCS 109/10 實作題第三題 題解