let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

QBMAX - Đường đi có tổng lớn nhất

solution.md

Gọi \(f(i,j)\) là tổng lớn nhất khi đi đến ô \((i, j)\), ta có:

\[f(i, j) = max\{f(i-1,j-1), f(i,j-1), f(i+1,j-1)\} + a(i, j)\]

Khi cài đặt không cần phải khai báo thêm mảng f mà có thể dùng chung với mảng a.

Độ phức tạp: \(O(n^2)\)

main.cpp
Open in Github • Download 
#include <iostream>
using namespace std;

#define For(i,a,b) for (int i=a; i<=b; i++)

int a[102][102];

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int m, n;
    cin >> m >> n;
    For(j,0,n) a[0][j] = a[m+1][j] = -1e9;

    For(i,1,m) For(j,1,n) cin >> a[i][j];

    For(j,2,n) For(i,1,m) {
        a[i][j] += max(a[i-1][j-1], max(a[i][j-1], a[i+1][j-1]));
    }

    int result = -1e9;
    For(i,1,m) result = max(result, a[i][n]);

    cout << result;
    return 0;
}
Comments