skiing

時(shí)間限制：3000?ms ?|? 內(nèi)存限制：65535?KB 難度：5 描述

Michael喜歡滑雪百這并不奇怪， 因?yàn)榛┑拇_很刺激。可是為了獲得速度，滑的區(qū)域必須向下傾斜，而且當(dāng)你滑到坡底，你不得不再次走上坡或者等待升降機(jī)來載你。Michael想知道載一個(gè)區(qū)域中最長(zhǎng)底滑坡。區(qū)域由一個(gè)二維數(shù)組給出。數(shù)組的每個(gè)數(shù)字代表點(diǎn)的高度。下面是一個(gè)例子?
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

一個(gè)人可以從某個(gè)點(diǎn)滑向上下左右相鄰四個(gè)點(diǎn)之一，當(dāng)且僅當(dāng)高度減小。在上面的例子中，一條可滑行的滑坡為24-17-16-1。當(dāng)然25-24-23-...-3-2-1更長(zhǎng)。事實(shí)上，這是最長(zhǎng)的一條。
輸入

第一行表示有幾組測(cè)試數(shù)據(jù)，輸入的第二行表示區(qū)域的行數(shù)R和列數(shù)C(1 <= R,C <= 100)。下面是R行，每行有C個(gè)整數(shù)，代表高度h，0<=h<=10000。
后面是下一組數(shù)據(jù)；

輸出

輸出最長(zhǎng)區(qū)域的長(zhǎng)度。

樣例輸入

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

來源

經(jīng)典題目

上傳者

iphxer

簡(jiǎn)單深搜，配合動(dòng)態(tài)規(guī)劃。

# include <stdio.h> # include <string.h> int max(int a, int b){return a>b?a:b;} int n, m, map[101][101], dp[101][101], next[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; int dfs(int x, int y) {int i, mx, my;if(dp[x][y])return dp[x][y];for(i=0; i<4; ++i){mx = x + next[i][0];my = y + next[i][1];if(mx<1 || my<1 || mx>n || my>m)continue;if(map[mx][my] < map[x][y])dp[x][y] = max(dp[x][y], dfs(mx, my));}++dp[x][y];return dp[x][y]; } int main() {int t, i, j, imax;scanf("%d",&t);while(t--){imax = 0;memset(dp, 0, sizeof(dp));scanf("%d%d",&n,&m);for(i=1; i<=n; ++i)for(j=1; j<=m; ++j)scanf("%d",&map[i][j]);for(i=1; i<=n; ++i)for(j=1; j<=m; ++j)imax = max(dfs(i, j), imax);printf("%d\n",imax);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/junior19/p/6730086.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的NYOJ10: skiing（DFS + DP）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。