CSP-J复赛集训200分-300分必刷-csp-j-2020方格取数

#include <bits/stdc++.h> using namespace std; //dp算法 int n,m; const int N=1010; int a[N][N]; long long f[N][N]; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; } } /*dp求出走到每个点经过的数字和的最大值 一列一列求，对于每一列，求从上向下走到每个点经过的数字和的最大值 也要求从下向上走到每个点经过的数字和的最大值 然后取两者中的最大值 */ memset(f,-0x7f,sizeof(f)); long long ma;//走到每个格子经过的数字和最大值 f[1][0]=0;//初始化第一行第一列前面那个格子 for(int j=1;j<=m;j++){ //从上向下求 ma=-1e18; for(int i=1;i<=n;i++){ ma=max(ma,f[i][j-1])+a[i][j]; f[i][j]=max(f[i][j],ma); } //从下向上求 ma=-1e18; for(int i=n;i>=1;i--){ ma=max(ma,f[i][j-1])+a[i][j]; f[i][j]=max(f[i][j],ma); } } cout<<f[n][m]; return 0; }