前段時(shí)間寫(xiě)了PKU的滑雪，因?yàn)槭侵形牡谋容^好動(dòng)，想了一下直接過(guò)了，就像Mr_cai說(shuō)的所謂記憶化搜索就是 搜索+動(dòng)態(tài)規(guī)劃。記錄每一個(gè)點(diǎn)為起點(diǎn)開(kāi)始滑的最大值，然后遇到有記錄的坐標(biāo)就直接返回坐標(biāo)上的值。
         后來(lái)又去做HDU 的FatMouse and Cheese，英文描述。沒(méi)注意細(xì)節(jié)，與前一題不一樣的地方在于這題可以直著走<=K步，一旦停下來(lái)下一次又可以走<=K步。最后才知道的，還有就是老鼠每次都是從坐標(biāo)0,0出發(fā)。。居然沒(méi)看見(jiàn)，，導(dǎo)致我用了上面一樣的方法每個(gè)坐標(biāo)搜一次，超時(shí)，直到最后才發(fā)現(xiàn)這兩個(gè)問(wèn)題，可見(jiàn)仔細(xì)有多重要。

#include <iostream>
#include <cstring>
using namespace std;
int map[102][102];
int ans[102][102];
int n,m;
int dir[4][2]={0,1,1,0,0,-1,-1,0};
int dfs(int x,int y)
{
    if(ans[x][y]) return ans[x][y];
    int i,j,nx,ny;
    int temp,maxv=0;
    for(i=0;i<4;++i)
    {
        for(j=1;j<=m;++j)
        {
            nx = x+dir[i][0]*j;
            ny = y+dir[i][1]*j;
            if(nx>=1 && nx<=n && ny>=1 && ny<=n && map[nx][ny] > map[x][y])
            {
                temp = dfs(nx,ny);
                if (temp > maxv)
                {
                    maxv = temp;
                }
            }
        }
    }
    ans[x][y]=maxv+map[x][y];
    return ans[x][y];
}

int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        if(n==-1 && m==-1)break;
        memset(ans,0,sizeof(ans));
        memset(map,10,sizeof(map));
        for(i=1;i<=n;++i)
        {
            for(j=1;j<=n;++j)
            {
                scanf("%d",&map[i][j]);
            }
        }
        dfs(1,1);
        printf("%d\n",ans[1][1]);
    }
    return 0;
}