[HDOJ1078]FatMouse and Cheese(记忆化搜索)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1078

题意：给出n， k，然后给出n*n的地图，（下标0~n-1），有一只老鼠从(0,0)处出发，只能走直线，并且目标点的数值比当前点要大。每次最长可以走k步，问最长的一条链的数值和。

用一个二维数组dp(i,j)表示某一格出发的时候最长链的数值和，然后dfs。

 #include <algorithm>

 #include <iostream>

 #include <iomanip>

 #include <cstring>

 #include <climits>

 #include <complex>

 #include <fstream>

 #include <cassert>

 #include <cstdio>

 #include <bitset>

 #include <vector>

 #include <deque>

 #include <queue>

 #include <stack>

 #include <ctime>

 #include <set>

 #include <map>

 #include <cmath>

 using namespace std;

 const int maxn = ;

 const int dx[] = {, , , -};

 const int dy[] = {, -, , };

 int n, k;

 int G[maxn][maxn];

 int dp[maxn][maxn];

 bool ok(int x, int y) {

     return x >=  && y >=  && x < n && y < n;

 }

 int dfs(int x, int y) {

     if(dp[x][y]) return dp[x][y];

     int cur = ;

     for(int i = ; i < ; i++) {

         for(int j = ; j <= k; j++) {

             int xx = x + dx[i] * j;

             int yy = y + dy[i] * j;

             if(ok(xx, yy) && G[xx][yy] > G[x][y]) {

                 cur = max(cur, dfs(xx, yy));

             }

         }

     }

     return dp[x][y] = cur + G[x][y];

 }

 inline bool scan_d(int &num) {

     char in;bool IsN=false;

     in=getchar();

     if(in==EOF) return false;

     while(in!='-'&&(in<''||in>'')) in=getchar();

     if(in=='-'){ IsN=true;num=;}

     else num=in-'';

     while(in=getchar(),in>=''&&in<=''){

             num*=,num+=in-'';

     }

     if(IsN) num=-num;

     return true;

 }

 int main() {

     // freopen("in", "r", stdin);

     while(~scanf("%d%d", &n, &k) && n + k != -) {

         memset(dp, , sizeof(dp));

         for(int i = ; i < n; i++) {

             for(int j = ; j < n; j++) {

                 scan_d(G[i][j]);

             }

         }

         printf("%d\n", dfs(, ));

     }

     return ;

 }