https://vijos.org/p/1011

动态规划求解,但是每个数可能需要的时候还没求出来,所以要再递归把依赖的那些数先求完。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int fun(vector<vector<int>> &num, vector<vector<int>> &dp, int i, int j, int R, int C)
{
    int up = 0, down = 0, left = 0, right = 0;
    int maxn = 0;
    if ((i - 1 >= 0) && num[i][j] > num[i - 1][j])
    {
        // up
        up++;
        if (dp[i - 1][j] == 0)
        {
            dp[i - 1][j] = fun(num, dp, i - 1, j, R, C);
        }
        maxn = max(maxn, dp[i - 1][j] + 1);
    }
    if ((i + 1 <= R - 1) && num[i][j] > num[i + 1][j])
    {
        // down
        down++;
        if (dp[i + 1][j] == 0)
        {
            dp[i + 1][j] = fun(num, dp, i + 1, j, R, C);
        }
        maxn = max(maxn, dp[i + 1][j] + 1);
    }
    if ((j - 1 >= 0) && num[i][j] > num[i][j - 1])
    {
        // left
        left++;
        if (dp[i][j - 1] == 0)
        {
            dp[i][j - 1] = fun(num, dp, i, j - 1, R, C);
        }
        maxn = max(maxn, dp[i][j - 1] + 1);
    }
    if ((j + 1 <= C - 1) && num[i][j] > num[i][j + 1])
    {
        // right
        right++;
        if (dp[i][j + 1] == 0)
        {
            dp[i][j + 1] = fun(num, dp, i, j + 1, R, C);
        }
        maxn = max(maxn, dp[i][j + 1] + 1);
    }
    dp[i][j] = maxn;
    return dp[i][j];
}
int main()
{
    int R, C;
    cin >> R >> C;
    vector<vector<int>> num(R, vector<int>(C, 0));
    vector<vector<int>> dp(R, vector<int>(C, 0));

    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            cin >> num[i][j];
        }
    }
    int result = 0;
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            dp[i][j] = fun(num, dp, i, j, R, C);
            result = max(result, dp[i][j]);
        }
    }

    cout << result + 1 << endl;
    return 0;
}