学步园

s[i][j]表示i,j处的最大值，

s[i][j] = {s[i-k][j],s[i+k][j],s[i][j-k],s[i][j+k]}+ a[i][j]

用记忆化搜索，解为s[0][0]

#include <iostream> 
#include <cmath>
#include <cstring>
using namespace std;

int n,k;
int s[101][101];
int a[101][101];

int dirX[4] = {-1,0,1,0};
int dirY[4] = {0,1,0,-1};

int DP(int x,int y)
{
	int sum;
	int max1 = 0;
	if(s[x][y] > 0)
		return s[x][y];
	for(int i = 1; i <= k; i++)
	{
		for(int j = 0; j < 4; j++)
		{
			int xx = x + dirX[j]*i;
			int yy = y + dirY[j]*i;
			if(xx >= 0 && xx < n && yy >= 0 && yy < n && a[xx][yy] > a[x][y])
			{
				sum = DP(xx,yy);
				max1 = max(sum,max1);
			}
		}
	}
	s[x][y] = max1 + a[x][y];
	return s[x][y];
}


int main()
{	

	while(cin>>n>>k)
	{
		if(n == -1 && k == -1)
			break;
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			{
				cin>>a[i][j];
			}
		}

		memset(s,0,sizeof(s));

		int ans = DP(0,0);
		cout<<ans<<endl;
	}
	return 0;
}