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;
}（如果有误在评论区留言即可）