【正经题解】方格取数

不同于其他题只能走上右或下右，该题能走上下右，单凭普通的dp解决不了问题。

首先，我们思考，只能走右不能走左，意味着我们可以单独将每一列分开求解，而向右走其实是从某列运动到下一列，下一列再运动到下下一列……实质上是一个递推的过程。

然后对于每一列，我们会发现要么只能往上走，要么只能往下走。

为什么呢？

不能重复经过已经走过的方格。

说明我们不能往上走再往下走，这样就重复走了。同理也不能往下走再往上走。

这样就很好解了，设有两个数组up[i][j]和down[i][j]分别表示从下面走上来到i行j列时的最大值和从上面走下来到i行j列时的最大值。

当然，最大值也有可能是从左边过来的。

再设一个数组f[i][j]代表i行j列最终可取到的最大值。

然后a[i][j]代表i行j列的方格的元素。

所以状态转移方程就可以写出来了：

up[i][j]=max(up[i+1][j],f[i][j-1])+a[i][j];

down[i][j]=max(down[i-1][j],f[i][j-1])+a[i][j];

f[i][j]=max(up[i][j],down[i][j]);

发现最大值仅与上一列的最大值有关，所以可以降一维：

up[i]=max(f[i],up[i+1])+a[i][j];

down[i]=max(f[i],down[i-1])+a[i][j];

f[i]=max(down[i],up[i]);

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
int a[1001][1001];
long long up[1005],down[1005],f[1005];
inline int read(){
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return f*x;
}
int main(){
//	freopen("number.in","r",stdin);
//	freopen("number.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
		a[i][j]=read();
	f[1]=a[1][1];
	for(int i=2;i<=n;i++) f[i]=f[i-1]+a[i][1];
	for(int j=2;j<m;j++){
		memset(down,0,sizeof(down));
		memset(up,0,sizeof(up));
		down[1]=f[1]+a[1][j];up[n]=f[n]+a[n][j];
		for(int i=2;i<=n;i++) down[i]=max(f[i],down[i-1])+a[i][j];
		for(int i=n-1;i>=1;i--) up[i]=max(f[i],up[i+1])+a[i][j];
		for(int i=1;i<=n;i++) f[i]=max(down[i],up[i]);
	}
	f[1]+=a[1][m];
	for(int i=2;i<=n;i++) f[i]=max(f[i],f[i-1])+a[i][m];
	printf("%lld",f[n]);
	return 0;
}