503
hdu 1078 FatMouse and Cheese 記憶化搜索
一開始打算正向用狀態dp，結果果斷超時，換成反向記憶話搜索就過了
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
int map[105][105];
int n,k;
int dp[105][105];
int dir[4][2]={1,0,-1,0,0,1,0,-1};
int ans;
int walk(int x,int y)
{
if(dp[x][y])return dp[x][y];
int i,j;
int nx,ny,t=0;
for(i=0;i<4;i++)
{
nx=x;ny=y;
for(j=0;j<k;j++)
{
nx+=dir[i][0];ny+=dir[i][1];
if(nx<=0||ny<=0||nx>n||ny>n)break;
if(map[nx][ny]>map[x][y])
t=max(t,walk(nx,ny));
}
}
dp[x][y]=t+map[x][y];
return dp[x][y];
}
int main()
{
while(~scanf("%d%d",&n,&k)&&n+1)
{
memset(map,-1,sizeof(map));
memset(dp,0,sizeof(dp));
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&map[i][j]);
}
printf("%d\n",walk(1,1));
}
}
最後更新：2017-04-03 18:51:47