AcWing 901. 滑雪
原题链接
简单
作者:
henhen敲
,
2020-04-26 15:53:48
,
所有人可见
,
阅读 517
import java.io.*;
class Main{
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int nextInt()throws Exception{
in.nextToken();
return (int)in.nval;
}
static int R, C;
static int[][] f, w;
static int[] x = {0, 0, -1, 1};
static int[] y = {1, -1, 0, 0};
static int DP(int i, int j){
if(f[i][j]>0) return f[i][j];
for(int k=0; k<4; k++){
if(j+x[k]>-1&&i+y[k]>-1&&i+y[k]<R&&j+x[k]<C&&w[i][j]>w[i+y[k]][j+x[k]])
f[i][j] = Math.max(f[i][j], DP(i+y[k], j+x[k])+ 1);
}
return f[i][j];
}
public static void main(String[] args)throws Exception{
R = nextInt(); C = nextInt();
f = new int[R][C];
w = new int[R][C];
for(int i=0; i<R; i++)
for(int j=0; j<C; j++)
w[i][j] = nextInt();
int res = 0;
for(int i=0; i<R; i++)
for(int j=0; j<C; j++)
res = Math.max(res, DP(i, j)+1);
out.print(res);
out.close();
}
}