To solve this problem, we need to maximize the sum of numbers collected from two paths starting at the top-left corner (1,1) and ending at the bottom-right corner (n,n) of an n x n grid. Each path can only move right or down, and cells visited by both paths are counted once.

Approach

The key insight is to use dynamic programming (DP) to track the maximum sum for two paths simultaneously. Here's the detailed approach:

1. State Definition: We define dp[k][x1][x2] as the maximum sum obtained when the first path reaches (x1, y1) and the second path reaches (x2, y2) after k steps. Here, y1 = k + 2 - x1 and y2 = k + 2 - x2 (since each step increases the sum of coordinates by 1).

2. Transitions: For each state, the previous state can come from four possible combinations of moves (down/right for both paths):

   • Both paths move down: dp[k-1][x1-1][x2-1]
   • First path down, second path right: dp[k-1][x1-1][x2]
   • First path right, second path down: dp[k-1][x1][x2-1]
   • Both paths move right: dp[k-1][x1][x2]

3. Value Calculation: If both paths are at the same cell, add the cell value once; otherwise, add both cell values.

4. Initialization: The initial state dp[0][1][1] is the value of the starting cell (1,1).

5. Final State: The result is dp[2n-2][n][n] (since it takes 2n-2 steps to reach the bottom-right corner from the top-left).

Solution Code

n = int(input())
grid = [[0] * (n + 1) for _ in range(n + 1)]

# Read grid values until 0 0 0 is encountered
while True:
    a, b, c = map(int, input().split())
    if a == 0 and b == 0 and c == 0:
        break
    grid[a][b] = c

max_k = 2 * n - 2
# Initialize DP array: dp[k][x1][x2]
dp = [[[0] * (n + 2) for _ in range(n + 2)] for __ in range(max_k + 1)]
dp[0][1][1] = grid[1][1]

for k in range(1, max_k + 1):
    for x1 in range(1, n + 1):
        y1 = k + 2 - x1
        if y1 < 1 or y1 > n:
            continue
        for x2 in range(1, n + 1):
            y2 = k + 2 - x2
            if y2 < 1 or y2 > n:
                continue
            # Get maximum value from all possible previous states
            current_max = 0
            # Up-Up
            if x1 - 1 >= 1 and x2 - 1 >= 1:
                current_max = max(current_max, dp[k-1][x1-1][x2-1])
            # Up-Right
            if x1 - 1 >= 1:
                current_max = max(current_max, dp[k-1][x1-1][x2])
            # Right-Up
            if x2 - 1 >= 1:
                current_max = max(current_max, dp[k-1][x1][x2-1])
            # Right-Right
            current_max = max(current_max, dp[k-1][x1][x2])

            # Add the value of current cells
            if x1 == x2:
                current_max += grid[x1][y1]
            else:
                current_max += grid[x1][y1] + grid[x2][y2]

            dp[k][x1][x2] = current_max

print(dp[max_k][n][n])

Explanation

• Grid Input: The grid is read using a loop until 0 0 0 is encountered, which marks the end of input.
• DP Initialization: The starting state is set to the value of the top-left cell.
• DP Transition: For each step k, we compute the maximum sum for all valid positions of the two paths, considering all possible previous moves.
• Result: The final result is the maximum sum when both paths reach the bottom-right corner, which is stored in dp[2n-2][n][n].

This approach efficiently computes the desired result with a time complexity of O(n³) (since k ranges up to 2n-2, and x1/x2 range up to n), which is feasible for the given problem constraints. The space complexity is O(n³) (for the 3D DP array), but it can be optimized to O(n²) by using two 2D arrays (previous and current states). However, the 3D array is easier to understand and implement for beginners.

作者声明:本文包含人工智能生成内容。