$\text{Ý tưởng}$

Bài toán này là tìm đường đi có tổng điểm lớn nhất từ cột $\text{0}$ đến cột $\text{n + 1}$ trên bẳng 3 hàng (1,2,3) dự vào quy luật của đề

+ Nhảy cột: Từ cột $\text{i}$ chỉ được chảy tới cột $\text{j}$ nếu khoảng cách từ 1 đến $\text{p}$. Do đó, khi tính cho cột $\text{j}$, ta chỉ cần xét các cột $\text{i}$ trước đó trong khoảng từ $\text{max (0 , j - p)}$ đến $\text{j - 1}$

+ Đổi hàng: Từ hàng giữa (hàng 2) bắt buộc phải nhảy sang hàng biên (hàng 1 hoặc 3)

.Ngược lại,  từ hàng biên (hàng 1 hoặc 3) bắt bộc phải nhảy về hàng giữa (hàng 2

$\text{Công thức}$

Gọi $\text{f [j] [r]}$ là điểm lớn nhất khi đến cột $\text{j}$ ở hàng $\text{r}$ (r ∈ {1,2,3})

Khởi tạo

+f[0][1] = f[0][2] = f[0][3] = 0(xuất phát từ cột 0 với 0 điểm )

+Tất cả các ô còn lại được đặt bằng  $\text{-INF}$ (chưa thể đi đến)

Chuyển trặng thái: Với mỗi cột j (từ 1 đến n + 1), duyệt lại các cột i hớpleej trước đó (limit <= i < j)

+Đén hàng giữa : $\text{f[j][2] = max({f[j][2], f[i][1] + c[2][j], f[i][3] + c[2][j]})}$

+Đến hàng biên 1: $\text{f[j][1] = max(f[j][1], f[i][2] + c[1][j])}$

+Đến hàng biên 3: $\text{f[j][3] = max(f[j][3], f[i][2] + c[3][j])}$

Kết quả: $\text{kq = max({f[n + 1][1], f[n + 1][2], f[n + 1][3]})}$ (giá trị lớn nhất tại ô kết thức cột n + 1)

$\text{C++}$

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const long long INF = 1e17;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //tối ưu IO và input
    int n, p;ios_base::sync_with_stdio(0); cin.tie(0);
    if (!(cin >> n >> p)) return 0;
    vector<vector<long long>> c(4, vector<long long>(n + 2, 0));
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> c[i][j];
        }
    }
    // khởi tạo qhđ
    vector<vector<long long>> f(n + 2, vector<long long>(4, -INF));
    f[0][1] = f[0][2] = f[0][3] = 0;
    //hai vòng lặp lồng nhau
    for (int j = 1; j <= n + 1; j++) {
        int limit = max(0, j - p);
        for (int i = limit; i < j; i++) {
            if (f[i][1] != -INF) f[j][2] = max(f[j][2], f[i][1] + c[2][j]);
            if (f[i][3] != -INF) f[j][2] = max(f[j][2], f[i][3] + c[2][j]);
            if (f[i][2] != -INF) {
                f[j][1] = max(f[j][1], f[i][2] + c[1][j]);
                f[j][3] = max(f[j][3], f[i][2] + c[3][j]);
            }
        }
    }
    //tìm kết quả
    long long kq = max({f[n + 1][1], f[n + 1][2], f[n + 1][3]});
    cout << kq << "\n";
    return 0;
}