求助-怎么优化?
查看原帖
求助-怎么优化?
77106
甜菜根楼主2020/11/11 20:18
//T470
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3ff3f3f3f;
ll dp[1010][1010];
ll a[1010][1010];
ll st[1010];
ll n,m;
int main(){
//	freopen("number.in","r",stdin);
//	freopen("number.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			scanf("%lld",&a[i][j]);
            dp[i][j]=-inf;
		}
	}
	dp[n-1][m-1]=a[n-1][m-1];
	for(int i=n-2;i>=0;i--){
		dp[i][m-1]=a[i][m-1]+dp[i+1][m-1];
	}
	for(int j=m-2;j>=0;j--){
		memset(st,0,sizeof st);
		for(int i=0;i<n;i++){
			st[i]=st[max(0,i-1)]+a[i][j];
		}
		for(int i=0;i<n;i++){
			for(int ii=0;ii<n;ii++){
				dp[i][j]=max(dp[i][j],dp[ii][j+1]+st[max(ii,i)]-st[min(ii,i)]+a[min(ii,i)][j]);
			}
		}
	}
	cout<<dp[0][0];
	return 0;
}

TLE 70

2020/11/11 20:18
加载中...