HDU 1078 FatMouse and Cheese【记忆化搜索】

 

第一次做记忆化搜索的问题 查找了网上的资料

参考了网上对记忆化搜索的解释

 

1.记忆化搜索的思想

记忆化搜索的思想是,在搜索过程中，会有很多重复计算,如果我们能记录一些状态的答案，就可以减少重复搜索量

2、记忆化搜索的适用范围

根据记忆化搜索的思想，它是解决重复计算，而不是重复生成，也就是说，这些搜索必须是在搜索扩展路径的过程中分步计算的题目，也就是“搜索答案与路径相关”的题目，而不能是搜索一个路径之后才能进行计算的题目，必须要分步计算，并且搜索过程中，一个搜索结果必须可以建立在同类型问题的结果上，也就是类似于动态规划解决的那种。

也就是说，他的问题表达，不是单纯生成一个走步方案，而是生成一个走步方案的代价等，而且每走一步，在搜索树/图中生成一个新状态，都可以精确计算出到此为止的费用，也就是，可以分步计算，这样才可以套用已经得到的答案

3、记忆化搜索的核心实现

a.首先，要通过一个表记录已经存储下的搜索结果，一般用哈希表实现

b.状态表示，由于是要用哈希表实现，所以状态最好可以用数字表示，常用的方法是把一个状态连写成一个p进制数字，然后把这个数字对应的十进制数字作为状态

c.在每一状态搜索的开始，高效的使用哈希表搜索这个状态是否出现过，如果已经做过，直接调用答案，回溯//这个就是标记 优化加速

d.如果没有，则按正常方法搜索

4、记忆化搜索是类似于动态规划的，不同的是，它是倒做的“递归式动态规划”。

 

 

fatmouse and cheese

time limit: 2000/1000 ms (java/others)memory limit: 65536/32768 k (java/others)
total submission(s): 8104accepted submission(s): 3388


problem description

 

fatmouse has stored some cheese in a city. the city can be considered as a square grid of dimension n: each grid location is labelled (p,q) where 0 <= p < n and 0 <= q < n. at each grid location fatmouse has hid between 0 and 100 blocks of cheese in a hole. now he's going to enjoy his favorite food.

fatmouse begins by standing at location (0,0). he eats up the cheese where he stands and then runs either horizontally or vertically to another location. the problem is that there is a super cat named top killer sitting near his hole, so each time he can run at most k locations to get into the hole before being caught by top killer. what is worse -- after eating up the cheese at one location, fatmouse gets fatter. so in order to gain enough energy for his next run, he has to run to a location which have more blocks of cheese than those that were at the current hole.

given n, k, and the number of blocks of cheese at each grid location, compute the maximum amount of cheese fatmouse can eat before being unable to move.

 

 

input

 

there are several test cases. each test case consists of

a line containing two integers between 1 and 100: n and k
n lines, each with n numbers: the first line contains the number of blocks of cheese at locations (0,0) (0,1) ... (0,n-1); the next line contains the number of blocks of cheese at locations (1,0), (1,1), ... (1,n-1), and so on.
the input ends with a pair of -1's.

 

 

output

 

for each test case output in a line the single integer giving the number of blocks of cheese collected.

 

 

sample input

 

3 1 1 2 5 10 11 6 12 12 7 -1 -1

 

 

sample output

 

37

 

 

 

 

 

#include
#include
#include
#include
#define max 105
#define max(a,b)  a>b?a:b
using namespace std;
int map[max][max],vis[max][max];
int step[4][2]={0,1,0,-1,1,0,-1,0};
int max_zi,n,k,nx,ny;
int dps(int x,int y)
{
    int maxx=0;//每次必须初始最大值
    if(vis[x][y]!=0) return vis[x][y];//如果是已经计算过 就不用再计算
    for(int i=0;i<4;i++)//四个方向遍历
    {
        for(int j=1;j<=k;j++)//每个方向走k个单位
        {
            nx=x+step[i][0]*j;
            ny=y+step[i][1]*j;
            if(nx>=0&&ny>=0&&nxmap[x][y])//新的数一定要大于之前的数 符合题意
                {
                    max_zi=dps(nx,ny);//找出下一个dfs的最大值
                    maxx=max(maxx,max_zi);//挑选出这个点中遍历的最大值
                }
            }
        }
    }
    return vis[x][y]=map[x][y]+maxx;//各个方向各个点中最大的数+当前点的数
}
int main(void)
{
    while(~scanf("%d%d",&n,&k))
    {
        memset(vis,0,sizeof(vis));
        if(n==-1||k==-1)
        {
            return 0;
        }
        for(int i=0;i