2020-CSP-J-T4方格取数 题解

小熊从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。小熊会取走所有经过的方格中的整数，求它能取到的整数之和的最大值。

注意：$1 \le n,m \le 10^3$，方格中整数的绝对值不超过 $10^4$,它能取到的整数之和的最大值为 $10^3$* $10^3$$*$$10^4$即$10^{10}$

所以dp数组定义为long long 类型，不妨所有数组都定义为long long类型。

n行m列格子的值存到a数组

const int N=1000+10,M=1000+10;
long long a[N][M];
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        scanf("%lld",&a[i][j]);
    }
}

思路1：

从左上角开始搜索，每个格子有三个邻接点，$1 \le n,m \le 10^3$，到右下角 搜索执行次数最多为$3^{10^6}$，超时！

思路2:

如果题目是 “只能：往下走 或 往右走“

为了能从第一行 第一列开始推，可以先把dp数组初始化为极小值，方格中整数的绝对值不超过 $10^4$,它能取到的整数之和的最大值为 $10^3 $* $10^3$$*$$10^4$即$10^{10}$，极小值为$-10^{10}$-1

long long dp[N][M];//dp[i][j]：从起点(1,1)到(i,j)的整数之和最大值
//按行推
dp[1][1]=a[1][1];//初始值
for(int i=1;i<=n;i++){//行
    for(int j=1;j<=m;j++){//列
        if(i==1&&j==1) continue;
        dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];//递推公式
    }
}

//按列推
long long dp[N][M];//dp[i][j]：从起点(1,1)到(i,j)的整数之和最大值
dp[1][1]=a[1][1];//初始值
for(int j=1;j<=m;j++){//列
    for(int i=1;i<=n;i++){//行
         if(i==1&&j==1) continue;
         dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];//递推公式 
    }
}

加上向上走会多哪些走法呢？

因为不能重复经过已经走过的方格，不会出现 走上去 再下来 再上去 这种情况，

向上走到达绿色点处一定是从粉色点走上来的，粉色点又是从当前位置左边或者下边上来的，如上图所示，和上面分析的向右向下类似，即向右向上走。

也正是因为不能重复经过已经走过的方格，所以第一列只能从(1,1）向下走

dp数组第一列一定是从（1,1）向下走得到的，

dp[1][1]=a[1][1];
for(int i=2;i<=n;i++) {
    dp[i][1]=dp[i-1][1]+a[i][1];
}

又因为 每一步只能向上、向下或向右走一格,不会往左走，我们可以一列一列推，

即推到第j列时，前j-1列都推好了。

到达第i行第j列 分成2种情况讨论 ：

①向右向下走到达的；

②向右向上走到达的。

对于第2列~第m列：

①向右向下走 行从1到n

dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];//递推公式 向右向下走

②向右向上走 行从n到1

dp[i][j]=max(dp[i+1][j],dp[i][j-1])+a[i][j];//递推公式 向右向上走

对于一列来说 向右向下走 和 向右向上走 这一列推出来的值是互不影响的，可以都推完后

(i,j)位置谁推出来的值大就选择谁。

只有一个dp数组 一列中 向右向上走推的时候 会直接覆盖 向右向下走推 的值，没办法2类都推出来比较了。

如何做呢？

可以再定义2个数组。

const int N=1000+10,M=1000+10;
long long  up[N][M],down[N][M],dp[N][M],a[N][M];
//up[i][j]: 从起点(1,1)到(i,j)第j列向上向右整数之和最大值
//down[i][j]: 从起点(1,1)到(i,j)第j列向下向右整数之和最大值
//dp[i][j]:从起点(1,1)到(i,j)的整数之和最大值 

j从第2列开始到第m列

对于每一列，i从第1行-->第n行推出 $down[i][j]$

for(int i=1;i<=n;i++){
    down[i][j]=max(down[i-1][j],dp[i][j-1])+a[i][j];
    //i==1时候 down数组看第0行 所以down数组也要和dp数组一样初始化为极小值
}

for(int i=n;i>=1;i--){
    up[i][j]=max(up[i+1][j],dp[i][j-1])+a[i][j];	
    //i==n时候 up数组看第n+1行 所以up数组也要和dp数组一样初始化为极小值
}

当第j列的$down[][]$和$up[][]$都推好后，这一列相同位置$down[][]$和$up[][]$比较，$dp[i][j]$为2者最大值。

for(int i=1;i<=n;i++) {
    dp[i][j]=max(down[i][j],up[i][j]);	
}

dp数组第j列就推好了。

整体代码

	//推出第2列--->第m列
	for(int j=2;j<=m;j++){
		for(int i=1;i<=n;i++){
			down[i][j]=max(down[i-1][j],dp[i][j-1])+a[i][j];
		
		}
		for(int i=n;i>=1;i--){
			up[i][j]=max(up[i+1][j],dp[i][j-1])+a[i][j];	
		}
		for(int i=1;i<=n;i++) {
			dp[i][j]=max(down[i][j],up[i][j]);	
		}
	}

推完后，$dp[n][m]$就是答案

【参考代码】

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1000+10,M=1000+10;
long long  up[N][M],down[N][M],dp[N][M],a[N][M];
//up[i][j]: 从起点(1,1)到(i,j)第j列向上向右整数之和最大值
//down[i][j]: 从起点(1,1)到(i,j)第j列向下向右整数之和最大值
//dp[i][j]:从起点(1,1)到(i,j)的整数之和最大值 
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%lld",&a[i][j]);
			
		}
	}
	for(int i=0;i<=n+1;i++){
		for(int j=0;j<=m+1;j++){
				//if(i==0||i==n+1)
				up[i][j]=down[i][j]=dp[i][j]=-1e10-1;//初始值 
		}
	}
	//只能向上、向下或向右走一格 
	//第一列 一定是向下走得到的，推出第一列 
	dp[1][1]=a[1][1];
	for(int i=2;i<=n;i++) {
		dp[i][1]=dp[i-1][1]+a[i][1];
	}
	//推第2列-->第m列 
	for(int j=2;j<=m;j++){
		//第j列的down数组元素  
		for(int i=1;i<=n;i++){
			down[i][j]=max(down[i-1][j],dp[i][j-1])+a[i][j];
		
		}
		//第j列的up数组元素 
		for(int i=n;i>=1;i--){
			up[i][j]=max(up[i+1][j],dp[i][j-1])+a[i][j];	
		}
		//根据up和down第j列 推出 dp数组第j列 
		for(int i=1;i<=n;i++) {
			dp[i][j]=max(down[i][j],up[i][j]);	
		}
		
	}
	cout<<dp[n][m];
	return 0;
}