HDU - 1078 FatMouse and Cheese

再谈记忆化搜索

题目描述：
FatMouse has stored some cheese in a city. The city can be considered as a square grid of dimension n: each grid location is labelled (p,q) where 0 <= p < n and 0 <= q < n. At each grid location Fatmouse has hid between 0 and 100 blocks of cheese in a hole. Now he’s going to enjoy his favorite food.

FatMouse begins by standing at location (0,0). He eats up the cheese where he stands and then runs either horizontally or vertically to another location. The problem is that there is a super Cat named Top Killer sitting near his hole, so each time he can run at most k locations to get into the hole before being caught by Top Killer. What is worse – after eating up the cheese at one location, FatMouse gets fatter. So in order to gain enough energy for his next run, he has to run to a location which have more blocks of cheese than those that were at the current hole.

Given n, k, and the number of blocks of cheese at each grid location, compute the maximum amount of cheese FatMouse can eat before being unable to move.

Input

There are several test cases. Each test case consists of a line containing two integers between 1 and 100: n and k n lines, each with n numbers: the first line contains the number of blocks of cheese at locations (0,0) (0,1) … (0,n-1); the next line contains the number of blocks of cheese at locations (1,0), (1,1), … (1,n-1), and so on. The input ends with a pair of -1’s.

Output
For each test case output in a line the single integer giving the number of blocks of cheese collected.

Sample Input
3 1
1 2 5
10 11 6
12 12 7
-1 -1
Sample Output
37
思路分析：
题目大概的意思就是输入一个n和一个k，n代表地图维度，k代表每次走的最大步数，求一条路径上的数值最大和。本题需要注意，只能沿着一个方向走，不能出现拐弯的情况，即只能横着走，或者竖着走，且只能走比上一个点数值大的点。
大概实现：

for(int i=0;i<4;i++){
        for(int j=1;j<=m;j++){
            tx=x+dir[i][0]*j;
            ty=y+dir[i][1]*j;

既然是记忆化搜索，那么一定要用到DP的思路，dp在这里面表示什么呢？他表示的是该点到终点经过的每条路径上和最大值。即答案可用dp[1][1]来表示，当然我们dfs(1,1)也是答案，后面就知道了。思路就是，枚举在当前点能走到的每一个点，然后记录下每次的答案，即temp，最后在回溯的过程中，我们要选出最大值。这个过程中我们有个剪枝，即依据题意，比上一次小的点不走。
dfs代码如下：

int dfs(int x,int y){
    int tx,ty,kmax=0;
    if(dp[x][y]!=-1) return dp[x][y];
    for(int i=0;i<4;i++){
        for(int j=1;j<=m;j++){
            tx=x+dir[i][0]*j;
            ty=y+dir[i][1]*j;
            if(check(tx,ty)&&a[tx][ty]>a[x][y]){
                temp=dfs(tx,ty);
                if(kmax<temp) kmax=temp;
            }
        }
    }
    dp[x][y]=a[x][y]+kmax;
    return dp[x][y];
}

完整代码展示：

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int dir[4][2]={0,1,1,0,0,-1,-1,0};
int n,m,temp;
int a[105][105];
int dp[105][105];
int check(int x,int y){
    if(x<1||y<1||x>n||y>n) return 0;
    else return 1;
}
int dfs(int x,int y){
    int tx,ty,kmax=0;
    if(dp[x][y]!=-1) return dp[x][y];
    for(int i=0;i<4;i++){
        for(int j=1;j<=m;j++){
            tx=x+dir[i][0]*j;
            ty=y+dir[i][1]*j;
            if(check(tx,ty)&&a[tx][ty]>a[x][y]){
                temp=dfs(tx,ty);
                if(kmax<temp) kmax=temp;
            }
        }
    }
    dp[x][y]=a[x][y]+kmax;
    return dp[x][y];
}
int main(){
    while(cin>>n>>m){
        if(n==-1&&m==-1) return 0;
        memset(dp,-1,sizeof dp);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                cin>>a[i][j];
        cout<<dfs(1,1)<<endl;
    }
    return 0;
}