前段时间写了PKU的滑雪，因为是中文的比较好动，想了一下直接过了，就像Mr_cai说的所谓记忆化搜索就是 搜索+动态规划。记录每一个点为起点开始滑的最大值，然后遇到有记录的坐标就直接返回坐标上的值。
后来又去做HDU 的FatMouse and Cheese，英文描述。没注意细节，与前一题不一样的地方在于这题可以直着走<=K步，一旦停下来下一次又可以走<=K步。最后才知道的，还有就是老鼠每次都是从坐标0,0出发。。居然没看见，，导致我用了上面一样的方法每个坐标搜一次，超时，直到最后才发现这两个问题，可见仔细有多重要。
#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;
}
posted on 2011-04-15 13:55
mr_chen 阅读(215)
评论(0) 编辑 收藏 引用 所属分类:
搜索