hdu1078 HDU1078 DFS記憶化搜索－IT工程師數位筆記本

文章出處

HDU1078 DFS記憶化搜索：在n*n的地圖上，每個格子都有若干奶酪，老鼠從（0，0）出發，每次只能朝一個方向運動1到k次，且到達的下一個格子奶酪一定要比這個多，求最多能吃到的奶酪數。

思路：dfs即可，由于還要枚舉每一次移動的步數，重復計算很多，因此需要保存之前的結果。

記憶化搜索：算法上依然是搜索的流程，但是搜索到的一些解用動態規劃的那種思想和模式作一些保存。一般說來，動態規劃總要遍歷所有的狀態，而搜索可以排除一些無效狀態。更重要的是搜索還可以剪枝，可能剪去大量不必要的狀態，因此在空間開銷上往往比動態規劃要低很多。記憶化算法在求解的時候還是按著自頂向下的順序，但是每求解一個狀態，就將它的解保存下來，以后再次遇到這個狀態的時候，就不必重新求解了。這種方法綜合了搜索和動態規劃兩方面的優點，因而還是很有實用價值的。（百度百科）

#include#include#include#include#include#includeusing namespace std;#define INF  0x3f3f3f3ftypedef long long  LL;int d[2][4]={-1,0,0,1,0,-1,1,0};int dp[101][101],g[101][101],n,k;int dfs(int x,int y){//返回從(x,y)出發能夠得到的最大值    if(dp[x][y])return dp[x][y];    for(int i=0;i<4;++i){        for(int j=1;j<=k;++j){//平移1~k格            int dx=x+d[0][i]*j,dy=y+d[1][i]*j;            if(dx>=0&&dx=0&&dyg[x][y]){                dp[x][y]=max(dp[x][y],g[x][y]+dfs(dx,dy));            }        }    }    if(!dp[x][y])dp[x][y]=g[x][y];//這個位置還是0，說明到了遞歸終點，同一行同一列沒有更大的了    return dp[x][y];}int main(){    while(scanf("%d%d",&n,&k),(n+1)||(k+1)){        for(int i=0;i;++i){>&&g[dx][dy]>&&dy>

看文倉www.kanwencang.com網友整理上傳,為您提供最全的知識大全,期待您的分享，轉載請注明出處。
歡迎轉載：http://www.kanwencang.com/bangong/20170125/95190.html

文章列表