luoguP1434滑雪

 题目描述

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。下面是 R行，每行有 C$个数，代表高度(两个数字之间用 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

输出 
25

 说明/提示

对于 100% 的数据，1<=R,C<=100。

 还是这道题，记忆化搜索已经讲完了他的题目解法，见（1）中的题目做法，但两种算法的PK仍然在继续，因为动态规划还没有出场！

有请动态规划！

记忆化搜索和我十分相似，甚至我们两个可以互相替代，我的时间更短，所以记忆化搜索应该输在我手上。至于这题，我的方法需要两个辅助，堆和opreator.

operator是一个提供运算符重载的东西，他较为复杂，常用于struct或class，本人喜欢用struct。

struct node{int x,y,val;bool operator>(const node& o)const{return val>o.val;}
};

 由于代码过于难，我也调了一天，就不让你们痛苦了。

堆也很简单，stl大法好！

priority_queue<node,vector<node>,greater<node> >q;

 输入时要把该点高度扔进堆里，初始化dp[i][j]=1。

 重头戏在dp，dp无后效性，所以要从小到大进行 dp,由于dp[i][j]的定义是在i，j这个点做滑雪起点时能滑的最大坡，所以从小到大的顺序不会有后效性。然后维护方向数组，像搜索一样扩展。

代码如下：

#include<bits/stdc++.h>
using namespace std;
struct node{int x,y,val;bool operator>(const node& o)const{return val>o.val;}
};
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int a[1001][1001],n,dp[1001][1001],m;
priority_queue<node,vector<node>,greater<node> >q;
int main(){cin>>n>>m;for (int i=1;i<=n;i++){for (int j=1;j<=m;j++){cin>>a[i][j];q.push({i,j,a[i][j]});dp[i][j]=1;}}while (q.size()){int x=q.top().x,y=q.top().y,val=q.top().val;q.pop();int k=dp[x][y];for (int i=0;i<4;i++){int xx=dx[i]+x,yy=dy[i]+y;if (val>a[xx][yy]){dp[x][y]=max(dp[x][y],k+dp[xx][yy]);}}}int ans=0;for (int i=1;i<=n;i++){for (int j=1;j<=m;j++){ans=max(ans,dp[i][j]);}}cout<<ans<<endl;return 0;
}

（如果有误在评论区留言即可）