hdu1078 记忆化搜索

题意：

给你n*n的地图 每个格子有一个值只能从值小的格子走到值较大的格子 给你k每次上下左右最多走k步 问你走的格子最大值的是多少

dp【i】【j】表示以（i，j）为起点的能得到的最大值 然后深搜求解

#include
  
   
#include
   
     #include
     
     using namespace std
     ; int n
     ,k
     ,dp
     [110
     ][110
     ],cost
     [110
     ][110
     ]; int dir
     [4
     ][2
     ]={0
     ,1
     ,0
     ,-1
     ,1
     ,0
     ,-1
     ,0
     }; int mark
     [110
     ][110
     ]; int max
     (int a
     ,int b
     ) { return a
     >b
     ?a
     :b
     ; } int dfs
     (int x
     ,int y
     ) { int i
     ,j
     ,sum
     =0
     ; for(i
     =1
     ;i
     <=k
     ;i
     ++) { for(j
     =0
     ;j
     <4
     ;j
     ++) { int xx
     =x
     +dir
     [j
     ][0
     ]*i
     ; int yy
     =y
     +dir
     [j
     ][1
     ]*i
     ; if(xx
     <0
     ||xx
     >=n
     ||yy
     <0
     ||yy
     >=n
     ) continue; if(cost
     [xx
     ][yy
     ]<=cost
     [x
     ][y
     ]) continue; if(mark
     [xx
     ][yy
     ]) { sum
     =max
     (sum
     ,dp
     [xx
     ][yy
     ]); } else { mark
     [xx
     ][yy
     ]=1
     ; sum
     =max
     (sum
     ,dfs
     (xx
     ,yy
     )); } } } dp
     [x
     ][y
     ]=cost
     [x
     ][y
     ]+sum
     ; return dp
     [x
     ][y
     ]; } int main() { int i
     ,j
     ; while(~scanf
     ("%d%d"
     ,&n
     ,&k
     )) { if(n
     <0
     ) break; for(i
     =0
     ;i
     <n
     ;i
     ++) for(j
     =0
     ;j
     <n
     ;j
     ++) { scanf
     ("%d"
     ,&cost
     [i
     ][j
     ]); } memset
     (dp
     ,0
     ,sizeof(dp
     )); memset
     (mark
     ,0
     ,sizeof(mark
     )); mark
     [0
     ][0
     ]=1
     ; printf
     ("%d\n"
     ,dfs
     (0
     ,0
     )); } return 0
     ; }