Maximum sum of 2 paths on a matrix

Revision en6, by goldenskygiang, 2019-04-08 17:12:09

You're given a matrix $$$A$$$ of size $$$N * M$$$, consisting of integers satisfying $$$|A_{i,j}| \leqslant 100$$$. Rows are numbered $$$1$$$ to $$$N$$$ downward, and columns are numbered $$$1$$$ to $$$N$$$ from left to right. There are 2 players, each one will move from block $$$(1, 1)$$$ to block $$$(N, M)$$$ and can only move to the right or downward. 2 paths made by the 2 players can only have $$$(1, 1)$$$ and $$$(N, M)$$$ as two common blocks. All other blocks in the 2 paths must be distinct. Find the 2 paths that have maximum sum when combined.

Input: the first line consists of 2 numbers $$$N$$$ and $$$M$$$. $$$(N, M \leqslant 200)$$$

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

This problem was included in an offline contest that I participated yesterday. Other contestants said that this is a DP problem but I couldn't figure out the solution.

Tags dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English goldenskygiang 2019-04-08 17:12:09 3 Tiny change: 'are numbers $1$ to $N' -> 'are numbered $1$ to $N'
en5 English goldenskygiang 2019-04-08 07:17:59 23 Tiny change: '$ and $M$.\n\nNext $' -> '$ and $M$. $(N, M \leqslant 200)$\n\nNext $'
en4 English goldenskygiang 2019-04-07 19:24:44 14 Tiny change: 'aximum sum.\n\n**Inp' -> 'aximum sum when combined.\n\n**Inp'
en3 English goldenskygiang 2019-04-07 19:24:14 8 Tiny change: 'All other points in the 2' -> 'All other blocks in the 2'
en2 English goldenskygiang 2019-04-07 19:23:06 429 Tiny change: '|A_{i,j}| <= 100$. The' -> '|A_{i,j}| \leqslant 100$. The' (published)
en1 English goldenskygiang 2019-04-07 15:18:26 681 Initial revision (saved to drafts)