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.
Auto comment: topic has been updated by goldenskygiang (previous revision, new revision, compare).
This is a very old problem from codeforces. You can solve it with dynamic programming on diagonals,
dp[diag][p1][p2] -> max sum of two paths
, wherediag
— number of diagonal (row_id
+col_id
),p1
— position of first player on current diagonal,p2
— position of second player on current diagonal.But in that problem, players can have common points
Yes, you need to forbid common points in dp
Yep
What are the bounds on N?
Sorry I forgot that, $$$N, M \leqslant 200$$$
So the base idea of the solution is to build the two paths simultaneously and basically looks like this:
Now you have to apply DP on top of this. Naively doing
dp[x1][y1][x2][y2]
will obviously lead to $$$O(N^2M^2)$$$. The trick is to realize that since the two paths are not independent, i.e. they move forwards at the same speed, you can dodp[moves][y1][y2]
andx1 = moves - y1
x2 = moves - y2
. This is $$$O((N+M)N^2)$$$.(Depending on if you opt for 0-indexing or 1-indexing you may need a +/-1 here and there.)