hdu 1078 记忆化搜索

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 #include<map>
 8 using namespace std;
 9 #define MOD 1000000007
10 const double eps=1e-5;
11 #define cl(a) memset(a,0,sizeof(a))
12 #define ts printf("*****\n");
13 const int MAXN=1005;
14 int n,m,tt;
15 int dp[MAXN][MAXN],k;
16 int a[MAXN][MAXN];
17 int d[4][2]={0,-1,-1,0,1,0,0,1};
18 int dfs(int x,int y)    //从xy点出发所能得到的最大
19 {
20     int nx,ny,max1=0;
21     if(dp[x][y])    return dp[x][y];
22         for(int i=0;i<4;i++)
23             for(int j=1;j<=k;j++)
24             {
25                 nx=x+d[i][0]*j;
26                 ny=y+d[i][1]*j;
27                 if(nx>=0&&nx<n&&ny>=0&&ny<n&&a[nx][ny]>a[x][y])
28                 {
29                     int sum=dfs(nx,ny);
30                     max1=max(max1,sum);
31                 }
32             }
33     return dp[x][y]=max1+a[x][y];
34 }
35 int main()
36 {
37     int i,j;
38     #ifndef ONLINE_JUDGE
39     freopen("1.in","r",stdin);
40     #endif
41     while(scanf("%d%d",&n,&k)!=EOF)
42     {
43         if(n==-1&&k==-1)    break;
44         for(i=0;i<n;i++)
45             for(j=0;j<n;j++)    scanf("%d",&a[i][j]);
46         cl(dp);
47         dfs(0,0);
48         printf("%d\n",dp[0][0]);
49     }
50 }