ski.java

PKU中一些数据结构基本算法题的java实现

package PKU.DP;
import java.util.Scanner;


/**
 * ID:1088
 * 动态规划
 * @author yhm
 *
 */
public class Ski {

	static int R = 0;
	static int C = 0;
	static int[][] M;
	static int[][] IN;
	static int[] REdge = {1,-1,0,0};
	static int[] CEdge = {0,0,1,-1};
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			R = cin.nextInt();
			C = cin.nextInt();
			M = new int[R][C];
			IN = new int[R][C];
			for(int i=0;i<R;i++){
				for(int j=0;j<C;j++){
					IN[i][j] = cin.nextInt();
					M[i][j] = -1;
				}
			}
			solve();
			
		}

	}

	static void solve(){
		int max = 0;
		for(int i=0;i<R;i++){
			for(int k=0;k<C;k++){
				int x = get(i, k);
				max=Math.max(x, max);
			}
		}
		System.out.println(max+1);
	}
	
	static int get(int r, int c){
		if(M[r][c]!=-1){
			return M[r][c];
		}
		
		
		int max = -1;
		for(int i=0;i<4;i++){
			int newR = r+REdge[i];
			int newC = c+CEdge[i];
			if(newR<0 || newR>=R || newC<0 || newC>=C){
				continue;
			}
			if(IN[newR][newC]<IN[r][c]){
				max = Math.max(get(newR,newC), max);
			}
		}
		if(max==-1){
			M[r][c] = 0;
		}
		else{
			M[r][c] = max+1;
		}
		return M[r][c];
	}
	
}