滑雪DP

待我称王封你为后i 2022-03-19 09:10 166阅读 0赞

## 题目描述 ##

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（从24开始，在1结束）。当然25－24－23－...－3－2－1更长。事实上，这是最长的一条。

## 输入输出格式 ##

**输入格式：**

输入的第一行为表示区域的二维数组的行数R和列数C（1≤R，C≤100）。下面是R行，每行有C个数，代表高度(两个数字之间用1个空格间隔)。

**输出格式：**

输出区域中最长滑坡的长度。

## 输入输出样例 ##

**输入样例\#1：** 复制

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

**输出样例\#1：** 复制

思路 ：吧所有的点升序排序，dp\[ i \] \[ j \]表示 i , j 的最大值。dp\[ i \]\[ j \]=  i , j 四周的点的比它低的点的最大的dp值+1   ，如果四个点都比它高 那么为  1；

代码

#include<bits/stdc++.h>
    	using namespace std;
    	struct Node{
    		int i,j,x;
    	};
    	bool cmp(Node x,Node y){
    		return x.x<y.x;
    	}
    	int a[105][105],f[105][105];
    	Node k[10005];
    	int main(){
    		int x,y,n,m,index=0,maxv,result=0;
    		Node e;
    		memset(a,0x3f3f3f3f,sizeof(e));
    		cin>>n>>m;
    		for(int i=1;i<=n;i++){
    			for(int j=1;j<=m;j++){
    				cin>>a[i][j];
    				e.i=i;e.j=j;
    				e.x=a[i][j];
    				k[++index]=e;	
    			}
    		}
    		sort(k+1,k+index+1,cmp);
    		bool flag;
    		for(int i=1;i<=index;i++){
    			e=k[i];
    			x=e.i;
    			y=e.j;
    			maxv=0;
    			if(a[x-1][y]<e.x&&maxv<f[x-1][y]){
    				maxv=f[x-1][y];
    			}
    			
    			if(a[x+1][y]<e.x&&maxv<f[x+1][y]){
    				maxv=f[x+1][y];
    			}
    			if(a[x][y-1]<e.x&&maxv<f[x][y-1]){
    				maxv=f[x][y-1];
    			}
    			if(a[x][y+1]<e.x&&maxv<f[x][y+1]){
    				maxv=f[x][y+1];
    			}
    			f[x][y]=maxv+1;
    			if(result<f[x][y])result=f[x][y];
    		}
    	//	for(int i=1;i<=index;i++)cout<<k[i].x<<" ";cout<<endl; 
    	//	for(int i=1;i<=n;i++){
    	//		for(int j=1;j<=n;j++)	
    	//			cout<<f[i][j];
    	//		cout<<endl;
    	//	}
    			
    		cout<<result;
    		return 0;
    	}