求助!P7074第19个点超时
  • 板块学术版
  • 楼主sw1tch
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/10/14 16:19
  • 上次更新2023/10/27 07:35:22
查看原帖
求助!P7074第19个点超时
606948
sw1tch楼主2022/10/14 16:19
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,a[1010][1010];
ll f[1010][1010],up[1010][1010],down[1010][1010];

int main() {
//	freopen("P7074_19.in","r",stdin);
//	freopen("PP.out","w",stdout);
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			cin>>a[i][j];
		}
	}
	f[1][1]=a[1][1];
	for(int i=2; i<=n; i++) {
		f[i][1]=f[i-1][1]+a[i][1];
	}
//	for(int i=2; i<=m; i++) {
//		f[1][i]=f[1][i-1]+a[1][i];
//	}

	for(int j=2; j<=m; j++) {
		memset(down,0,sizeof(down));
		memset(up,0,sizeof(up));
		down[1][j]=a[1][j]+f[1][j-1];
		up[n][j]=a[n][j]+f[n][j-1];
		for(int i=2; i<=n; i++) {
			down[i][j]=max(f[i][j-1],down[i-1][j])+a[i][j];
		}
		for(int i=n-1; i>=1; i--) {
			up[i][j]=max(f[i][j-1],up[i+1][j])+a[i][j];
		}
		for(int i=1;i<=n;i++)f[i][j]=max(up[i][j],down[i][j]);
	}
	
//	for(int j=1;j<=m;j++){
//		for(int i=1;i<=n;i++){
//			cout<<down[i][j]<<" "<<up[i][j]<<" "<<f[i][j];
//			cout<<endl;
//		}
//	}
	
	cout<<f[n][m];
	return 0;
}
2022/10/14 16:19
加载中...