###description

Một người trượt tuyết có tên là Michael muốn tìm chuỗi trượt dài nhất trên một khu vực雪山 được mô tả bởi một ma trận hai chiều. Mỗi phần tử trong ma trận biểu diễn độ cao của một điểm. Michael có thể trượt từ một điểm sang một trong bốn điểm lân cận (trên, dưới, trái, phải) nếu và chỉ nếu độ cao giảm xuống. Mục tiêu là tìm độ dài của chuỗi trượt dài nhất có thể.

###example

####example input

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

####example output

25

###approach

Vấn đề này có thể được giải quyết bằng phương pháp DFS (Tìm kiếm sâu) đi kèm với bộ nhớ hóa (memoization) để lưu trữ các kết quả đã tính toán. Sử dụng một ma trận dp để lưu trữ độ dài chuỗi trượt dài nhất bắt đầu từ mỗi điểm. Mỗi khi tính toán một điểm, chúng ta sẽ kiểm tra bốn hướng xung quanh và nếu điểm đó có độ cao thấp hơn, chúng ta sẽ đệ quy tính toán độ dài chuỗi trượt từ đó.

###solution code

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

int r, c, i, j, a[110][110], dp[110][110];
int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

int calculateMaxPath(int x, int y) {
    if (dp[x][y] != 1) {
        return dp[x][y];
    }
    for (int k = 0; k < 4; ++k) {
        int newX = x + directions[k][0];
        int newY = y + directions[k][1];
        if (newX >= 1 && newX <= r && newY >= 1 && newY <= c && a[x][y] > a[newX][newY]) {
            dp[x][y] = max(dp[x][y], calculateMaxPath(newX, newY) + 1);
        }
    }
    return dp[x][y];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> r >> c;
    for (i = 1; i <= r; ++i) {
        for (j = 1; j <= c; ++j) {
            cin >> a[i][j];
            dp[i][j] = 1;
        }
    }
    
    int maxLength = 0;
    for (i = 1; i <= r; ++i) {
        for (j = 1; j <= c; ++j) {
            maxLength = max(maxLength, calculateMaxPath(i, j));
        }
    }
    
    cout << maxLength << endl;
    return 0;
}

###explanation

1. Ma trận dp: Mỗi phần tử dp[i][j] biểu diễn độ dài chuỗi trượt dài nhất bắt đầu từ điểm (i, j). Ban đầu, giá trị của mỗi phần tử được đặt là 1, vì mỗi điểm ít nhất là một phần tử của chính nó.

2. Hướng di chuyển: Mảng directions lưu trữ bốn hướng di chuyển có thể (xuống, lên, phải, trái).

3. Hàm đệ quy calculateMaxPath: Hàm này sẽ kiểm tra các hướng di chuyển có thể từ điểm (x, y). Nếu một hướng di chuyển đến một điểm có độ cao thấp hơn, hàm sẽ gọi chính nó để tính toán độ dài chuỗi trượt từ điểm đó và cập nhật giá trị lớn nhất cho dp[x][y].

4. Tối ưu hóa đầu vào/đầu ra: Sử dụng các hàm ios::sync_with_stdio(false) và cin.tie(nullptr) để tăng tốc độ đọc và viết dữ liệu.

5. Tính toán độ dài lớn nhất: Sau khi đọc và khởi tạo ma trận, chúng ta duyệt qua mỗi điểm và gọi hàm calculateMaxPath để tìm độ dài chuỗi trượt lớn nhất.