hdu 1078 FatMouse and Cheese

Problem

acm.hdu.edu.cn/showproblem.php?pid=1078

题意

n * n 个洞，每个洞都放有 0 ~ 100 个芝士块。

老鼠从 （0，0）出发，每次都能横着或竖着走最多 k 格，且要走到芝士块数比当前洞多的洞里。

老鼠每次都吃完洞里的芝士块。问最多能吃多少块。

Analysis

位置（i，j）的洞，应该是从该洞的上、下、左、右四个方向 k 步之内的、芝士块比当前洞少的洞走过来的。所以到洞（i，j）能吃到的最多芝士块数：

dp[i][j] = cheese[i][j] + max { dp[i+dx][j] , dp[i][j+dy] | 0 <= i+dx , j+dy < n , -k <= dx , dy <= k }

可以用记忆化搜索写出这个 dp。但是这样在 dp[0~n-1][0~n-1] 找答案时，不知道哪些答案是从（0，0）出发得出的。

可以反过来想：从任意点出发，只能去芝士块数比当前洞小的洞，最后答案就是 dp[0][0]。

Source code

Accepted

#include <stdio.h>
#include <string.h>
#define N 100

int hole[N][N], dp[N][N], n, k;

int max(int a, int b)
{
	return a > b ? a : b;
}

int dfs(int r, int c)
{
	int i;
	if(dp[r][c] >= 0)
		return dp[r][c];
	dp[r][c] = 0; // 别忘了这句，因为下面的循环可能找不到合法的点，则最后 dp[r][c] = hole[r][c]
	for(i=1; i<=k; ++i)
	{
		if(r >= i && hole[r][c] < hole[r-i][c])
			dp[r][c] = max(dp[r][c], dfs(r-i, c));
		if(r+i < n && hole[r][c] < hole[r+i][c])
			dp[r][c] = max(dp[r][c], dfs(r+i, c));
		if(c >= i && hole[r][c] < hole[r][c-i])
			dp[r][c] = max(dp[r][c], dfs(r, c-i));
		if(c+i < n && hole[r][c] < hole[r][c+i])
			dp[r][c] = max(dp[r][c], dfs(r, c+i));
	}
	return dp[r][c] += hole[r][c];
}

int main()
{
	while(scanf("%d%d",&n,&k), ~n||~k)
	{
		int i, j;
		for(i=0; i<n; ++i)
			for(j=0; j<n; ++j)
				scanf("%d", hole[i]+j);
		memset(dp, -1, sizeof dp);
		printf("%d\n", dfs(0, 0));
	}
	return 0;
}

Wrong Answer（第一种想法）

#include <stdio.h>
#include <string.h>
#define N 100

int hole[N][N], dp[N][N], n, k;

int max(int a, int b)
{
	return a > b ? a : b;
}

int dfs(int r, int c)
{
	int i;
	if(dp[r][c] >= 0)
		return dp[r][c];
	for(i=1; i<=k; ++i)
	{
		if(r >= i && hole[r][c] > hole[r-i][c])
			dp[r][c] = max(dp[r][c], dfs(r-i, c) + hole[r][c]);
		if(r+i < n && hole[r][c] > hole[r+i][c])
			dp[r][c] = max(dp[r][c], dfs(r+i, c) + hole[r][c]);
		if(c >= i && hole[r][c] > hole[r][c-i])
			dp[r][c] = max(dp[r][c], dfs(r, c-i) + hole[r][c]);
		if(c+i < n && hole[r][c] > hole[r][c+i])
			dp[r][c] = max(dp[r][c], dfs(r, c+i) + hole[r][c]);
	}
	return dp[r][c];
}

int main()
{
	while(scanf("%d%d",&n,&k), ~n||~k)
	{
		int i, j, ans = 0;
		for(i=0; i<n; ++i)
			for(j=0; j<n; ++j)
				scanf("%d", hole[i]+j);
		memset(dp, -1, sizeof dp);
		dp[0][0] = hole[0][0];
		for(i=0; i<n; ++i)
			for(j=0; j<n; ++j)
				ans = max(ans, dfs(i, j));
		printf("%d\n", ans);
	}
	return 0;
}