題意：老鼠每次最多走k步停下來(lái)，停下的這個(gè)位置只能比上一個(gè)停留的位置大，并獲取其價(jià)值，每次只能水平或垂直走，問(wèn)最大能得到的價(jià)值解題思路：這道題可以用記憶化搜索解決，dp[i][j]表示老鼠在位置(i,j)時(shí)可以達(dá)到的最優(yōu)值。因?yàn)閐p的狀態(tài)是一個(gè)有向無(wú)環(huán)圖，剛開始想會(huì)不會(huì)走死循環(huán)，但是這道題有一個(gè)條件：下一個(gè)位置比當(dāng)前位置的值要大，所以說(shuō)既然能到當(dāng)前位置，那么之前的位置是不可能再次走到的。記憶化搜索實(shí)際上感覺(jué)就是在一顆解答樹上進(jìn)行剪枝，應(yīng)該算是一種搜索的策略。#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 100; int n,k,mat[maxn][maxn],dp[maxn][maxn]; int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};bool check(int x,int y,int newx,int newy) {if(newx < 0 || newx >= n || newy < 0 || newy >= n) return false;if(mat[x][y] >= mat[newx][newy]) return false;return true; }void dfsDP(int x,int y) {if(dp[x][y] != -1) return;for(int i = 0; i < 4; i++) //方向for(int j = 1; j <= k; j++) //步數(shù){int newx = x + j * dir[i][0];int newy = y + j * dir[i][1];if(check(x,y,newx,newy) == false) continue;dfsDP(newx,newy);dp[x][y] = max(dp[x][y],mat[x][y] + dp[newx][newy]);}if(dp[x][y] == -1) dp[x][y] = mat[x][y]; }int main() {while(scanf("%d%d",&n,&k)!=EOF){if(n == -1 && k == -1) break;for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)scanf("%d",&mat[i][j]);memset(dp,-1,sizeof(dp));dfsDP(0,0);printf("%d\n",dp[0][0]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 1078（记忆化搜索）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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