CSP-J 2020方格取数

• 今年CSP-J考挂了,int提交前脑残改long long导致T2爆零，T3两个小时没搞出来，爆零。T4想出正解，没时间了，爆零。
• 今年CSP-J考的痛苦极了~~~
• 好了，话不多说 明明说了很多
• 题干：蓝色的传送门

题干分析

• 这明显是dp，最正常不过的dp
• 上下右三个设置决定了要开三维数组（顶礼膜拜用二维（或更少）的大神们）
• 注意：方向向右不能向左，所以dp时要按列dp！！！，因为每一个格都只能走一次，所以要向上后不能向下，向下后不能向上。

具体思路

• 从右上向左下，先按列后按排dp（具体见代码）
• 然后要注意区分向上和向下，不能混杂

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long a[1005][1005],f[1005][1005][3];
int main(){
	memset(f,-64,sizeof(f));
	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[1][1][0]=f[1][1][1]=f[1][1][2]=a[1][1];
	for(int i=1;i<=m;i++){
		for(int j=1;j<n;j++)
			f[j+1][i][1]=max(f[j][i][0],f[j][i][1])+a[j+1][i];
		for(int j=n;j>1;j--)
			f[j-1][i][2]=max(f[j][i][0],f[j][i][2])+a[j-1][i];
		for(int j=1;j<=n;j++)
			f[j][i+1][0]=max(f[j][i][0],max(f[j][i][1],f[j][i][2]))+a[j][i+1];
	}
	long long ans=max(f[n][m][0],max(f[n][m][1],f[n][m][2]));
	printf("%lld\n",ans); 
	return 0;
}