Ý tưởng

Bài toán được giải bằng quy hoạch động (Dynamic Programming).

Ta sử dụng mảng ba chiều $F[i][j][k]$ để biểu diễn giá trị lớn nhất đạt được tại ô $(i, j)$ với đúng $k$ bước đi xuống liên tiếp ngay trước đó.

• $i$: chỉ số hàng hiện tại
• $j$: chỉ số cột hiện tại
• $k$: số bước đi xuống liên tiếp gần nhất (tối đa $2$ bước)

Khởi tạo

• Khởi tạo tất cả $F[i][j][k] = -1$ để biểu thị trạng thái chưa truy cập
• Gán $F[1][1][0] = a_{1,1}$ là điểm bắt đầu

Chuyển trạng thái

Với mỗi trạng thái hợp lệ $F[i][j][k] \ne -1$, ta xét 2 hướng đi:

1. Đi sang phải
   Nếu $j + 1 \le m$ thì: $$ F[i][j + 1][0] = \max\left(F[i][j + 1][0],\; F[i][j][k] + a_{i, j + 1}\right) $$ Vì không đi xuống nên $k = 0$

2. Đi xuống
   Nếu $i + 1 \le n$ và $k < 2$ thì: $$ F[i + 1][j][k + 1] = \max\left(F[i + 1][j][k + 1],\; F[i][j][k] + a_{i + 1, j}\right) $$

Kết quả

Kết quả là: $$ \max\left(F[n][m][0],\; F[n][m][1],\; F[n][m][2]\right) $$

Độ phức tạp

Với giới hạn $n, m \le 2025$, số trạng thái tối đa là:

$$ O(n \cdot m \cdot 3) = 2025 \cdot 2025 \cdot 3 \approx 12 \times 10^6 $$

Thuật toán đủ nhanh để chạy trong giới hạn thời gian.

Code

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    memset(F, -1, sizeof(F));
    F[1][1][0] = a[1][1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int k = 0; k <= 2; k++) {
                if (F[i][j][k] == -1) continue;

                // di sang phai
                if (j + 1 <= m)
                    F[i][j + 1][0] = max(F[i][j + 1][0], F[i][j][k] + a[i][j + 1]);

                // di xuong neu chua vuot qua 3 buoc lien tiep
                if (i + 1 <= n && k < 2)
                    F[i + 1][j][k + 1] = max(F[i + 1][j][k + 1], F[i][j][k] + a[i + 1][j]);
            }
        }
    }

    cout << max({F[n][m][0], F[n][m][1], F[n][m][2]});
}