Maximum sum of 2 paths on a matrix

Правка en1, от goldenskygiang, 2019-04-07 15:18:26

You're given a matrix A of size N * M, consisting of integers satisfying |A[i][j]| <= 100. There are 2 players, each one will move from point (1, 1) to point (N, M) and can only move to the right or downward (A[1][1] = A[N][M] = 0). 2 paths made by the 2 players can only have (1, 1) and (N, M) as two common points. All other points in 2 paths must be distinct. Find the 2 paths that have maximum sum.

Input: the first 2 numbers are N and M. Next N lines consist of M integers describing the matrix A. Note that A[1][1] = A[N][M] = 0. Output: The maximum sum of the 2 paths.

Example Input: 3 3 0 2 3 4 5 6 7 8 0

Example Output: 32

Теги dp

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский goldenskygiang 2019-04-08 17:12:09 3 Tiny change: 'are numbers $1$ to $N' -> 'are numbered $1$ to $N'
en5 Английский goldenskygiang 2019-04-08 07:17:59 23 Tiny change: '$ and $M$.\n\nNext $' -> '$ and $M$. $(N, M \leqslant 200)$\n\nNext $'
en4 Английский goldenskygiang 2019-04-07 19:24:44 14 Tiny change: 'aximum sum.\n\n**Inp' -> 'aximum sum when combined.\n\n**Inp'
en3 Английский goldenskygiang 2019-04-07 19:24:14 8 Tiny change: 'All other points in the 2' -> 'All other blocks in the 2'
en2 Английский goldenskygiang 2019-04-07 19:23:06 429 Tiny change: '|A_{i,j}| <= 100$. The' -> '|A_{i,j}| \leqslant 100$. The' (published)
en1 Английский goldenskygiang 2019-04-07 15:18:26 681 Initial revision (saved to drafts)