POJ 1088 动态规划

傷城~ 2022-06-13 10:49 162阅读 0赞

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