T4这样可以得70分,怎么优化?难道上单调队列?

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;
ll mat[1005][1005];
ll f[1005][1005];
ll sum[1005][1005];
int main()
{
	//freopen("number.in","r",stdin);
	//freopen("number.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mat[i][j];
			f[i][j] = -99999999;
		}
	}
	f[1][1] = mat[1][1];
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			sum[j][i] = sum[j-1][i]+mat[j][i];
		}
	}
	for(int i=2;i<=n;i++){
		f[i][1] = f[i-1][1]+mat[i][1];
	}
	for(int i=2;i<=m;i++){
		for(int j=1;j<=n;j++){
			f[j][i] = f[j][i-1]+mat[j][i];
			for(int k=1;k<=n;k++){
				if(k==j)continue;
				else if(k<j){
					f[j][i] = max(f[j][i],f[k][i-1]+sum[j][i]-sum[k-1][i]);
				}
				else{
					f[j][i] = max(f[j][i],f[k][i-1]+sum[k][i]-sum[j-1][i]);
				}
			}
		}
	}
	cout<<f[n][m]<<endl;
	return 0;
}

全部评论
是的吧
7 回复
分享
发布于 2020-12-07 20:28
你比赛写出了这个代码?
点赞 回复
分享
发布于 2020-11-07 21:24
百信银行
校招火热招聘中
官网直投
可以前缀和优化
点赞 回复
分享
发布于 2020-11-08 14:35
T3用gets编译错误?
点赞 回复
分享
发布于 2020-11-08 15:22
用dp,代码如下: #include<bits/stdc++.h> using namespace std; int n,m; long long a[1005][1005],f[1005][1005],f1[1005][1005],f2[1005][1005],f3[1005][1005]; int main(){ //freopen("number.in","r",stdin); //freopen("number.out","w",stdout); cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; for(int i=0;i<=n+1;i++) for(int j=0;j<=m+1;j++) f[i][j]=f1[i][j]=f2[i][j]=f3[i][j]=-1e18; for(int i=1;i<=n;i++){ long long sum=0; for(int k=1;k<=i;k++)sum+=a[k][1]; f[i][1]=sum; } for(int j=2;j<=m;j++){ for(int i=1;i<=n;i++) f1[i][j]=f[i][j-1]+a[i][j]; for(int i=2;i<=n;i++) f2[i][j]=max(f2[i-1][j],f1[i-1][j])+a[i][j]; for(int i=n-1;i>=1;i--) f3[i][j]=max(f1[i+1][j],f3[i+1][j])+a[i][j]; for(int i=1;i<=n;i++){ f[i][j]=max(f1[i][j],f2[i][j]); f[i][j]=max(f[i][j],f3[i][j]); } } printf("%lld",f[n][m]); //fclose(stdin); //fclose(stdout); return 0; }
点赞 回复
分享
发布于 2020-12-06 19:20

相关推荐

1 收藏 评论
分享
牛客网
牛客企业服务