package p1088; import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; public class Main { static int count=106; static int r; static int c; static int d[][] = new int[count][count]; static int lens[][] = new int[count][count]; public static void main(String[] args) throws FileNotFoundException { //File f = new File("c:\\data.txt"); //Scanner cin = new Scanner(f); Scanner cin = new Scanner(System.in); // 输入数据 r = cin.nextInt(); c = cin.nextInt(); for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { d[i][j] = cin.nextInt(); } } for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { // 对于每一个点都dp dp(i, j); } } int max = -Integer.MAX_VALUE; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (max < lens[i][j]) max = lens[i][j]; } } System.out.println(max); } static int dp(int i, int j) { // 记忆搜索。如果已经处理过,那么直接返回 if (lens[i][j] > 0) { return lens[i][j]; } int len1 = 0; int len2 = 0; int len3 = 0; int len4 = 0; if (j - 1 >= 0) { if (d[i][j - 1] < d[i][j]) { len1 = dp(i, j - 1); } } if (i - 1 >= 0) { if (d[i - 1][j] < d[i][j]) { len2 = dp(i - 1, j); } } if (j + 1 < c) { if (d[i][j + 1] < d[i][j]) { len4 = dp(i, j + 1); } } if (i + 1 < r) { if (d[i + 1][j] < d[i][j]) { len3 = dp(i + 1, j); } } // 记忆搜索 int tlen = 1 + get4max(len1, len2, len3, len4); lens[i][j] = tlen; return tlen; } static int get4max(int a, int b, int c, int d) { return max(a, b) > max(c, d) ? max(a, b) : max(c, d); } static int max(int a, int b) { return a > b ? a : b; } }
假设dp(i,j)表示i/j点到最低点的路径长度。
对于每一个点,有如下转移函数:
dp(i,j)=1+max{dp(i,j-1),dp(i-1,j),dp(i,j+1),dp(i+1,j)}
其中利用到记忆搜索。如果已经处理过的点,lens中不为0,直接返回即可。
-----------------------------------------------------------------------------------------------------------------------------------------------------------
题目描述
Description
Michael喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
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
一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。在上面的例子中,一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上,这是最长的一条。
Input
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行,每行有C个整数,代表高度h,0<=h<=10000。
Output
输出最长区域的长度。
Sample 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
Sample Output
25