方格取数题解

经验分享区
1

题目： P1004 [NOIP2000 提高组] 方格取数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题解中很多人只写了一种方法，我就浅浅地讲2种方法吧
更好的阅读： 方格取数题解 - 洛谷专栏 (luogu.com.cn)

记忆化

题目中说要走2次；一次从上往下，1次从下往上。我们可以将第2次想成从上往下走，那特殊条件就是if(dp[x1][y1][x2][y2]>=0)return dp[x1][y1][x2][y2];

结束条件就是if(x1==n&&y1==n&&x2==n&&y2==n)return a[n][n];

我们把DFS补全

int check(int x,int y){
	return x>=1&&y>=1&&x<=n&&y<=n;
}
int dfs(int x1,int y1,int x2,int y2){
	if(x1==n&&y1==n&&x2==n&&y2==n)return a[n][n];
	if(dp[x1][y1][x2][y2]>=0)return dp[x1][y1][x2][y2];
	int sum=0;
	for(int i=0;i<2;++i){
		for(int j=0;j<2;++j){
			int tx1=x1+dirx[i];
			int ty1=y1+diry[i];
			int tx2=x2+dirx[j];
			int ty2=y2+diry[j];
			if(check(tx1,ty1)&&check(tx2,ty2))sum=max(sum,dfs(tx1,ty1,tx2,ty2));
		}
	}
	if(x1==x2&&y1==y2)sum+=a[x1][y1];
	else sum+=a[x1][y1]+a[x2][y2];
	return dp[x1][y1][x2][y2]=sum;
}

其中的if(x1==x2&&y1==y2)sum+=a[x1][y1];是因为第一次走完后那个数就被取走了，第二次再取就是0
主函数很简单

int main(){
	scanf("%d",&n);
	memset(dp,-1,sizeof dp);
	while(1){
		scanf("%d%d%d",&x,&y,&z);
		if(x==0&&y==0&&z==0)break;
		a[x][y]=z;
	}
	printf("%d",dfs(1,1,1,1));
	return 0;
}

没啥好讲的

DP

最主要的是DP，而DP的4要素搞懂了DP就会写了
四要素就是

  1. 状态
  2. 转移方程
  3. 初始化
  4. 答案

带入本题就是

  1. 状态： dp[x1][y1][x2][y2] 表示走到 x1,y1,x2,y2 这个位置
  2. 转移方程：四种移动情况求 max
  3. 初始化： dp[0][0][0][0]=0
  4. 答案: dp[n][n][n][n]

按照这4个要素写就很简单了
Code

#include<bits/stdc++.h>
using namespace std;
int n;
int x,y,z;
int dp[10][10][10][10];
int a[10][10]
int main(){
	scanf("%d",&n);
	while(1){
		scanf("%d%d%d",&x,&y,&z);
		if(x==0&&y==0&&z==0)break;
		a[x][y]=z;
	}
	for(int x1=1;x1<=n;x1++){
		for(int y1=1;y1<=n;y1++){
			for(int x2=1;x2<=n;x2++){
				for(int y2=1;y2<=n;y2++){
					dp[x1][y1][x2][y2]=max(dp[x1-1][y1][x2-1][y2],max(dp[x1-1][y1][x2][y2-1],max(dp[x1][y1-1][x2-1][y2],dp[x1][y1-1][x2][y2-1])));
					if(x1==x2&&y1==y2)dp[x1][y1][x2][y2]+=a[x1][y1];
					else dp[x1][y1][x2][y2]+=a[x1][y1]+a[x2][y2];
				}
			}
		}
	}
	printf("%d",dp[n][n][n][n]);
	return 0;
}

当然还可以空间优化，但是没必要因为题目中说 1<=n<=9 空不空间优化都没关系，但如果 n 很大就要注意了，很多人空间优化都是背公式，将 n 维数组降为 n-1 维数组，这其实没意义我们不用背公式只要滚动数组来存 dp 就可以实现很理想的空间优化，而

滚动数组是神马呢

其实就是很简单就是根据题意找出一个 m 当你枚举到 i 时且 m=i*k+r (r<k) 则将这个数存到 r 这组中，本题的 m 很简单就是2，改一下代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int x,y,z;
int dp[2][10][10][10];
int a[10][10];
int main(){
	scanf("%d",&n);
	while(1){
		scanf("%d%d%d",&x,&y,&z);
		if(x==0&&y==0&&z==0)break;
		a[x][y]=z;
	}
	for(int x1=1;x1<=n;x1++){
		for(int y1=1;y1<=n;y1++){
			for(int x2=1;x2<=n;x2++){
				for(int y2=1;y2<=n;y2++){
					dp[x1%2][y1][x2][y2]=max(dp[(x1-1)%2][y1][x2-1][y2],max(dp[(x1-1)%2][y1][x2][y2-1],max(dp[x1%2][y1-1][x2-1][y2],dp[x1%2][y1-1][x2][y2-1])));
					if(x1==x2&&y1==y2)dp[x1%2][y1][x2][y2]+=a[x1][y1];
					else dp[x1%2][y1][x2][y2]+=a[x1][y1]+a[x2][y2];
				}
			}
		}
	}
	printf("%d",dp[n%2][n][n][n]);
	return 0;
}
1 个赞