算法训练 采油区域
2022/1/31 14:05:28
本文主要是介绍算法训练 采油区域,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
code
#include<iostream> #include<algorithm> using namespace std; const int N=1505; int s[N][N],a[N][N],b[N][N],c[N][N],d[N][N]; int ans,n,m,k; int main(){ ios::sync_with_stdio(false); cin>>n>>m>>k; int t; for(int i =1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>t,s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+t; } } for(int i=n;i>=k;i--){ //TODO for(int j=m;j>=k;j--){ //TODO s[i][j]-=s[i-k][j]+s[i][j-k]-s[i-k][j-k]; } } for(int i=k;i<=n;i++){ for(int j=k;j<=m;j++){ a[i][j]=max(s[i][j],max(a[i-1][j],a[i][j-1])); } } for(int i=k;i<=n;i++){ for(int j=m;j>=k;j--){ b[i][j]=max(s[i][j],max(b[i][j+1],b[i-1][j])); } } for(int i=n;i>=k;i--){ for(int j=k;j<=m;j++){ c[i][j]=max(s[i][j],max(c[i][j-1],c[i+1][j])); } } for(int i=n;i>=k;i--){ for(int j=m;j>=k;j--){ d[i][j]=max(s[i][j],max(d[i][j+1],d[i+1][j])); } } for(int i=k;i<=n-k;i++){//1 for(int j=k;j<=m-k;j++){ ans=max(ans,a[i][j]+b[i][j+k]+c[i+k][m]); } } for(int i=k+k;i<=n;i++){ for(int j=k;j<=m-k;j++){//2 ans=max(ans,c[i][j]+d[i][j+k]+a[i-k][m]); } } for(int i=k+k;i<=n-k;i++){ for(int j=k;j<=m;j++){//6 ans=max(ans,s[i][j]+a[i-k][m]+c[i+k][m]); } } for(int i=k;i<=n-k;i++){//3 for(int j=k;j<=m-k;j++){ ans=max(ans,a[i][j]+c[i+k][j]+b[n][j+k]); } } for(int i=k;i<=n-k;i++){//4 for(int j=k+k;j<=m;j++){ ans=max(ans,a[n][j-k]+b[i][j]+d[i+k][j]); } } for(int i=k;i<=n-k;i++){ for(int j=k+k;j<=m-k;j++){ ans=max(ans,s[i][j]+a[n][j-k]+b[n][j+k]); } } cout<<ans; return 0; }
ref
ref
这篇关于算法训练 采油区域的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!