前段時間寫了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 閱讀(218)
評論(0) 編輯 收藏 引用 所屬分類:
搜索