本文主要是介绍UVA 10913 - Walking on a Grid （记忆化搜索），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接~~>
做题感悟：开始不用标记数组把 dp 数组初始化一下用于标记但是这样因为初始化的原因就超时了，改为标记数组才过。
解题思路：记忆化搜索
这题很明显，如果用递推的方法的话必定不好写，因为在一行里可以向左做可以向右走，这样就导致不好递推，如果用记忆化方法的话就很好写了，如果单纯的只向右和下的话可以用三维标记 dp[ i ] [ j ] [ k ] (代表到达第i行第 j 列经历了 k 个负数所得到的最优值) ，这里还可以向左走，so~> 必须必须加一维方向，标记是从哪个方向得到的，放置重复走 ，即： dp [ i ] [ j ] [ k ] [ d ] 代表到达第 i 行第 j 列出现了 k 个负数从方向 d 得到的最优解。
代码：
#include<iostream>
#include<ctime>
#include<fstream>
#include<sstream>
#include<stack>
#include<cstring>
#include<map>
#include<vector>
#include<cstdio>
#include<algorithm>
#define INT long long int
using namespace std ;
const INT INF = 999999999 ;
const INT MY = 10 ;
const INT MX = 75 + 5 ;
INT n ,k ;
bool vis[MX][MX][MY][MY] ;
INT dp[MX][MX][MY][MY] ,g[MX][MX] ;
INT dx[4]={1 ,0 ,0} ,dy[4]={0 ,-1 ,1} ;
void input()
{for(INT i = 0 ;i < n ;i++)for(INT j = 0 ;j < n ;j++)scanf("%lld",&g[i][j]) ;memset(vis ,false ,sizeof(vis)) ;
}
INT DP_Memory(INT x ,INT y ,INT z ,INT d)
{if(z > k) return -INF ;if(x==n-1 && y == n-1)return g[x][y] ;if(vis[x][y][z][d])return dp[x][y][z][d] ;vis[x][y][z][d] = true ;INT& ans = dp[x][y][z][d] ;ans = -INF ;for(INT t = 0 ;t < 3 ;t++){INT sx = x + dx[t] ;INT sy = y + dy[t] ;if(d + t == 3) continue ;if(sx >= 0 && sy >= 0 && sx < n && sy < n){INT mx = (g[sx][sy] < 0) ;INT my = DP_Memory(sx ,sy ,z+mx ,t) ;if(my != -INF)ans = max(my + g[x][y] ,ans) ;}}return ans ;
}
int main()
{int cse = 1 ;while(scanf("%lld%lld",&n ,&k) ,n+k){input() ;INT x = (g[0][0] < 0) ,ans = -INF ;ans = DP_Memory(0 ,0 ,x ,0) ;cout<<"Case "<<cse++<<": " ;if(ans != -INF)cout<<ans<<endl ;else cout<<"impossible"<<endl ;}return 0 ;
}
这篇关于UVA 10913 - Walking on a Grid （记忆化搜索）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
