InputThere 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.
OutputFor 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
题意：
一步最多走k步，只能走到比当前值大的位置，问路径的权值最大和是多少？
思路：
相当明显的记忆化搜索，算是一个基本套路。
#include<iostream> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<map> #include<set> #include<cstdio> #include<cstring> #include<cmath> #include<ctime> #define fuck(x) cout<<#x<<" = "<<x<<endl; #define ls (t<<1) #define rs ((t<<1)+1) using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 100086; const int inf = 2.1e9; const ll Inf = 999999999999999999; const int mod = 1000000007; const double eps = 1e-6; const double pi = acos(-1); int dp[108][108]; int mp[108][108]; int n,k; int dfs(int x,int y){ if(dp[x][y]){return dp[x][y];} int &ret = dp[x][y]; ret=mp[x][y]; for(int i=1;i<=k;i++){ if(i+x<=n&&mp[i+x][y]>mp[x][y]){ret=max(ret,dfs(i+x,y)+mp[x][y]);} if(i+y<=n&&mp[x][i+y]>mp[x][y]){ret=max(ret,dfs(x,i+y)+mp[x][y]);} if(x-i>=1&&mp[x-i][y]>mp[x][y]){ret=max(ret,dfs(x-i,y)+mp[x][y]);} if(y-i>=1&&mp[x][y-i]>mp[x][y]){ret=max(ret,dfs(x,y-i)+mp[x][y]);} } return ret; } int main() { while(scanf("%d%d",&n,&k)&&(~n)&&(~k)){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ scanf("%d",&mp[i][j]); dp[i][j]=0; } } dfs(1,1); printf("%d\n",dp[1][1]); } return 0; }
HDU - 1078 FatMouse and Cheese (记忆化搜索）
原文：https://www.cnblogs.com/ZGQblogs/p/10664311.html
