简单记忆化 -- FatMouse and Cheese HDU - 1078

  • 时间:
  • 来源:互联网
  • 文章标签:

FatMouse and Cheese HDU - 1078

题意:
给你一个 n * n 的矩阵,每个格子都有一个权值,老鼠一步可以跨越1 ~ k个格子的距离,打下一个落脚的格子权值要大于现在的落脚格子,老鼠从(0, 0)出发,问老鼠经过格子权值和的最大值是多少。

思路:
显然dfs搜索,但我们可以用数组dp记忆化优化。dp[i][j]表示以(i, j)为落脚点的最优贡献。

code:


#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn = 1e2 + 5;
int a[maxn][maxn], dp[maxn][maxn];
int n, k;
int dx[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

void init(){
	memset(dp, -1, sizeof(dp));
}

int dfs(int x, int y){
	if(dp[x][y] != -1) return dp[x][y];  //最优贡献已经查找出来了,不需要再重复查找
	int mx = 0;
	for(int i = 1; i <= k; i++){
		for(int j = 0; j < 4; j++){
			int xx = x + dx[j][0] * i;
			int yy = y + dx[j][1] * i;
			if(xx >= 1 && xx <= n && yy >= 1 && yy <= n && a[xx][yy] > a[x][y])
			mx = max(mx, dfs(xx, yy));
		}
	}
	return dp[x][y] = a[x][y] + mx;  //记忆化
}

int main(){
	
	while(scanf("%d%d", &n, &k), n != -1 && k != -1){
		for(int i = 1; i <= n; i++)
		   for(int j = 1; j <= n; j++)
		      scanf("%d", &a[i][j]);
		      
		init();   
		
		int ans = dfs(1, 1);
		printf("%d\n", ans); 
	}
}

本文链接http://www.taodudu.cc/news/show-1781838.html