Vijos-清帝之惑之顺治-动态规划
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;
}