goldenskygiang's blog

By goldenskygiang, history, 9 months ago, In English,

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:


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.

Read more »

Tags dp
  • Vote: I like it
  • +1
  • Vote: I do not like it