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;
}

（如果有誤在評論區留言即可）