Ý 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(F[i][j+1][0],F[i][j][k]+a_{i,j+1})$$

   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(F[i+1][j][k+1],F[i][j][k]+a_{i+1,j})$$

Kết quả

Kết quả là:

Độ phức tạp

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

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]});
}