描述

給定一個n \times m \n×m??的矩陣，矩陣中的數字表示滑雪場各個區域的高度，你可以選擇從任意一個區域出發，并滑向任意一個周邊的高度嚴格更低的區域（周邊的定義是上下左右相鄰的區域）。請問整個滑雪場中最長的滑道有多長？(滑道的定義是從一個點出發的一條高度遞減的路線）。

(本題和矩陣最長遞增路徑類似，該題是當年NOIP的一道經典題)

數據范圍：?1 \le n,m \le 100 \1≤n,m≤100?，矩陣中的數字滿足?1 \le val \le 1000 \1≤val≤1000?

輸入描述：

第一行輸入兩個正整數 n 和 m 表示矩陣的長寬。
后續 n 行輸入中每行有 m 個正整數，表示矩陣的各個元素大小。

輸出描述：

輸出最長遞減路線。

示例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

復制說明：

從25出發，每次滑向周邊比當前小 1 的區域。 25->24->23->22->......->1 #include<stdio.h> #include<algorithm> #include<string.h> using namespace std; int a[105][105]; int dp[105][105]; int idx[105][105]; int direction[4][2]={{-1,0},{0,1},{1,0},{0,-1} }; int n,m; int find(int x,int y) {idx[x][y]=1;int maxx=0;for(int i=0;i<4;i++){int x1=direction[i][0]+x;int y1=direction[i][1]+y;if(a[x][y]<a[x1][y1]&&x1>=1 && x1<=n &&y1>=1&&y1<=m){if(idx[x1][y1]==-1){dp[x1][y1]=find(x1,y1);}if(dp[x1][y1]>maxx){maxx=dp[x1][y1];}}dp[x][y]=maxx+1;}return dp[x][y]; } int main() {memset(idx,-1,sizeof(idx));scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);}}int maxx=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){maxx=max(maxx,find(i,j));//表示從ij處出發最大下降的長度}}printf("%d\n",maxx);return 0; }

總結

以上是生活随笔為你收集整理的P18 滑雪的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。