Poj_1088_滑雪(DP)

一、Description(poj1088)

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

输出最长区域的长度。

二、问题分析

典型的DP问题，动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。

解这个问题与解其它的DP问题几乎没有什么两样。第一步找到问题的“状态”，第二步找到“状态转移方程”，然后基本上问题就解决了。首先，我们要找到这个问题中的“状态”是什么？我们必须注意到的一点是，到达一个坐标的方式最多有四种：上下左右四个方向，而且值必须必坐标值要大。然后再从这四个来源中选取符合要求的点，并从中选出S[i][j]最大的，也就是路径长度最长的，而所选出的这个坐标又可以当成是一个子问题递归求解。由于使用了记忆化存储，所以可以先直接查表，如果表中存在子问题的解则直接返回，否则就按上面的分析过程找到最大路径并存储。经过上面的分析，很容易可以得出问题的状态和状态转移方程。

S[i][j]=1 + max(S[i-1][j], if i>0 ; S[i][j-1], if j>0；S[i+1][j] , if i<m-1 ; S[i][j+1], if j<n-1 )

三、解决方案

有了上面的分析，编码就比较简单了。用一个二维数组用于读取坐标，再用一个二维数组用于记忆化存储。再写一个方法计算每一个坐标的值，并从四个方向分析上一步的最大值，并递归调用方法。算出本坐标的最大值并存储。最后，找出S数组中的最大值即是所求的最大路径。

import java.util.Scanner;

public class N1088_skate{

  private int h[][]=new int[101][101];

  private int m[][]=new int[101][101];

  private int r,c;

  private void init(){

    Scanner sc=new Scanner(System.in);

    r=sc.nextInt();

    c=sc.nextInt();

    for(int i=0;i<r;i++)

        for(int j=0;j<c;j++){

            h[i][j]=sc.nextInt();

    		m[i][j]=-1;

        }

  }

  //递归获取从点(i,j)出发滑行的最大长度

  public int searchWithMenmo(int x,int y){

		if( m[x][y]!=-1)

		    return m[x][y];

		else{

			int max=0;

			if(x>=1){

				if(h[x-1][y]>h[x][y]){

					max=Math.max(max,searchWithMenmo(x-1,y));

				}

			}

			if(y>=1){

				if(h[x][y-1]>h[x][y]){

					max=Math.max(max,searchWithMenmo(x,y-1));

				}

			}

			if(x<r-1){

				if(h[x+1][y]>h[x][y]){

					max=Math.max(max,searchWithMenmo(x+1,y));

				}

			}

			if(y<c-1){

				if(h[x][y+1]>h[x][y]){

					max=Math.max(max,searchWithMenmo(x,y+1));

				}

			}

			m[x][y]=max+1;

			return m[x][y];

	}

  }

 public int getMaxHeight(){

   int temp;

   int Max=-1;

   for(int i=0;i<r;i++){

        for(int j=0;j<c;j++){

            temp=searchWithMenmo(i,j);

            if(Max< temp)

                Max=temp;

        }

    }

    return Max;

  }

  public static void main(String args[]){

    N1088_skate m=new N1088_skate();

    m.init();

    System.out.println(m.getMaxHeight());

  	}

}

巴特西

Poj_1088_滑雪(DP)

最新文章

热门文章