小单刷题笔记之滑雪问题（DP）

描述

Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子

 1  2  3  4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。

输入

输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。

输出

输出最长区域的长度。

样例输入

5 51 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9

样例输出

25

思路：动态规划

1）我为人人式递推

         为了整理思路，我列了一个思维导图出来

1）首先我们分解子问题，明确状态，可以用maxLen（i，j）来表示坐标为i，j可以到达的最大距离。

2）想一下如果递推的话一定是由已知推未知，那什么是已知呢？我们稍加思考，一定是高度最低的点是已知，你想，高度最低的那个点，不可以向任何方向滑，那他的最大距离充其量也就是1，我们顺着这个思路往下想，那么我们就需要把所有的点按照高度来排序，不改变原坐标的情况下，我们就需要定义一个结构数组。

3）好OK，问题已经解决百分之70了，最后想一下状态转移方程。这里我用了所谓的我为人人式递推，想一下，周围四个点中筛选出高度比当前点高的那几个点，它至少可以是当前点最大距离+1，就是假设从那个点滑向当前点。也有可能那个点已经被更新了，所以递推公式应该是————maxLen（x2，y2）=max（maxLen（x2，y2），manLen(x1,y1)+1

接下来就是敲代码环节了，头脑要清醒~

#include#includeusing namespace std ;int n,m;int high[105][105];int maxLen[105][105];int d1[]={0,1,-1,0};int d2[]={1,0,0,-1};int ans=0;struct node{int x,y,h;//坐标 高度};node dp[10005];bool rule(node &a,node &b){//按照高度排序return a.h=1&&x=1&&y<=m)return true;//不能超出边界else return false;}void F(int index)//由低到高每一个点去推 {node a=dp[index];int x=a.x;int y=a.y;for(int i=0;ihigh[x][y]){//高度是否高于当前点maxLen[x1][y1]=max(maxLen[x1][y1],maxLen[x][y]+1);//递推式ans=max(ans,maxLen[x1][y1]);//更新答案，最长的就是answer}}}}int main(){cin>>n>>m;int index=0;for(int i=1;i<=n;i++){for(int j=1;j>high[i][j];dp[++index].h=high[i][j];dp[index].x=i;dp[index].y=j;maxLen[i][j]=1;//至少距离是1}}sort(dp+1,dp+index+1,rule);//从低到高排序for(int i=1;i<=index;i++){F(i);//由低到高更新每一个点周围的值} cout<<ans;return 0;}

if(check(x1,y1)){if(high[x1][y1]<a.h){maxLen[x][y]=max(maxLen[x][y],maxLen[x1][y1]+1);ans=max(ans,maxLen[x][y]);}}

#include#includeusing namespace std;int n,m;int maxLen[105][105];int high[105][105];int d1[]={1,0,-1,0};int d2[]={0,1,0,-1};int ans=0;struct node{int x,y,h;};node dp[10005];bool rule(node &a,node &b){return a.h=1&&x=1&&y<=m)return true;return false;}void F(int index){node a=dp[index];int x=a.x;int y=a.y;for(int i=0;i<4;i++){int x1=x+d1[i];int y1=y+d2[i];if(check(x1,y1)){if(high[x1][y1]>n>>m;int k=0;for(int i=1;i<=n;i++){for(int j=1;j>high[i][j];dp[++k].h=high[i][j];dp[k].x=i;dp[k].y=j;maxLen[i][j]=1;}}sort(dp+1,dp+k+1,rule);for(int i=1;i<=k;i++){F(i);}cout<<ans;}