題目鏈接

題意就不多解釋了，題目思路很簡單，搜索就行了，但是暴搜會TLE，但是對于每一個(gè)dfs（X, Y），如果參數(shù)一樣的話結(jié)果也是一樣的，我們用一個(gè)二維數(shù)組去保存每次計(jì)算的位置的結(jié)果，最后從所有的解里面挑出一個(gè)最大值即可。也許一開始考慮的時(shí)候會有這樣的想法，是不是從最高的位置開始找就能找到解，或者從最低的位置開始，起始不是這樣的，所以我們應(yīng)該去搜索每一個(gè)位置為起點(diǎn)的時(shí)候的解。

我還因?yàn)橐稽c(diǎn)小問題RE哭了，POJ不支持以下語法，闊以原諒，畢竟OJ很早了

return dp[x][y] = 1; #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int maxn = 110; int r, c, h[maxn][maxn], dp[maxn][maxn]; int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; namespace ans{const int inf = 0x3f3f3f3f;int dfs(int x, int y){if(dp[x][y] >= 0)return dp[x][y];int res = 0;int f = 0;for (int i = 0; i < 4; i++){int xx = x + dx[i];int yy = y + dy[i];if(xx >= 1 && xx <= r && yy >= 1 && yy <= c && h[xx][yy] < h[x][y]){res=max(res, dfs(xx, yy) + 1);f++;}}if(!f) {dp[x][y] = 1;return 1;}dp[x][y] = res;return res;}void MAIN(){scanf("%d %d", &r, &c);for (int i = 1; i <= r; i++){for (int j = 1; j <= c; j++){scanf("%d", &h[i][j]);}}int res = 0;memset(dp, -1, sizeof dp);for (int i = 1; i <= r; i++){for (int j = 1; j <= c; j++){int aans = dfs(i, j);res = max(aans, res);}}printf("%d\n", res);} } int main() {ans::MAIN();return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的poj 1088 滑雪 （dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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