[CSP-J2020]方格取数 详细题解

乍一看，这道题似乎与经典递推(dp)过河卒很像。可是仔细看，过河卒中的棋子可以向下或向右，而方格取数中的小熊可以向下、向右，还可以向上。
这意味着什么？
意味着对于每一个点，小熊可能是从下面过来的，也可能是从上面过来的，如图：

小熊既可以从红色路径抵达灰点，也可以从蓝色路径抵达灰点。
我们不知道小熊抵达某一个点是从上面，下面，或者左边过来的。因此，不能使用过河卒的方法推导。那怎么办呢？

将储存答案的数组增加一个维度。

设 f[i][j][k] 表示小熊走到 点$(i,j)$ 时能取到的最大整数和。

其中，$k$表示小熊到达这个点的方式。0表示小熊从这个点的下方过来，1表示小熊从这个点的上方过来。从左边过来的路径单独考虑，不需要专门为其赋一个$k$值。从左边来的路径已经包含在从上方或下方来的路径中。

这样，小熊的路像高架桥一样彼此错落开，路径就显得清晰了。

本题答案较大,要开 long long

我们采用记忆化搜索的方式，搜索一遍最大值。基本思想如下：
因为要求最大值，所以先将f数组赋值为一个最小值MIN（定义MIN=(-1)*2e18）

题难则反，如果从$(1,1)$开始搜索有点困难，那就运用逆向思维，从$(n,m)$开始搜索。

初始条件：走到点$(1,1)$的最大值只能为a[1][1]。因此，将 f[1][1][0] 和 f[1][1][1] 都赋为a[1][1]。

建立函数 search(int x,int y,int k) ，表示到达以$k$方式到达点$(x,y)$ 的最大值。

• 若 $(x,y)$ 超出 $n$ x $m$ 的方格范围，无解，返回MIN。
• 若 f[x][y][k] 不为MIN（即已经搜索到最大值），返回f[x][y][k]。
• 若k==0（从下方来），那就往下搜索，顺藤摸瓜寻找最大值。此时，小熊可能从下方来，也可能从左边来。而从左边来包含：从左边的上方来，从左边的下方- 来。因此，有三种情况需要搜索并取最大值：从正下方来，从左上方来，从左下方来。
• 若k==1（从上方来），那就往上搜索。同上，有三种情况需要搜索并取最大值：从正上方来，从左上方来，从左下方来。

由此可见，答案即为search(n,m,1)。

（此处k==1是因为$(n,m)$只能从上方或左边来，不能从下方来）

因为我们每次都把搜索得到的最大值存在f[x][y][k]，所以每个点都只需要搜一遍，时间复杂度$O(nm)$，可以AC。

AC代码

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1000+10;
const long long MIN=(-1)*2e18;
int n,m;
long long a[N][N],f[N][N][2];
long long mx(long long x,long long y,long long z){
	return x>max(y,z)?x:max(y,z);
}//定义mx函数，求三个数的最大值
long long search(long long x,long long y,long long k){
	if(x<1||x>n||y<1||y>m) return MIN;
	if(f[x][y][k]!=MIN) return f[x][y][k];
	if(k==0){
		f[x][y][k]=mx(search(x+1,y,0),search(x,y-1,0),search(x,y-1,1))+a[x][y];
	}else{
		f[x][y][k]=mx(search(x-1,y,1),search(x,y-1,0),search(x,y-1,1))+a[x][y];
	}
	return f[x][y][k];
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%lld",&a[i][j]);
			f[i][j][0]=MIN;
			f[i][j][1]=MIN;
		}
	}
	f[1][1][0]=a[1][1];
	f[1][1][1]=a[1][1];
	printf("%lld\n",search(n,m,1));
	return 0;
}

欢迎加入团队