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 100int 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 100int 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;}