AcWing 901. 滑雪
原题链接
简单
作者:
rushhhhh
,
2021-02-28 13:13:33
,
所有人可见
,
阅读 315
#include <iostream>
#include <cstring>
using namespace std;
/*
状态表示f[i,j]
集合:以[i,j]为起点的路径
属性:max
状态计算
每个结点可以往四个方向下滑
见视频。
*/
const int N = 310;
int n, m;
int g[N][N], f[N][N];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int dp(int x, int y)
{
int &v = f[x][y];
if(v != -1)
return v;
v = 1;
for(int i=0; i<4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if(nx>=1 && nx<=n && ny>=1 && ny<=m && g[nx][ny]<g[x][y])
v = max(v, dp(nx, ny) + 1);
}
return v;
}
int main()
{
cin >> n >> m;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
cin >> g[i][j];
memset(f, -1, sizeof f);
int res = 0;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
res = max(res, dp(i, j));
cout << res;
return 0;
}