啧……明明以前做到过这种类型的题结果全忘了……
这种矩阵的,一般都是先枚举行,然后对列进行一遍单调队列,搞出右下角在每一行中合法位置时的最小权值
再枚举列,对行做一遍单调队列,用之前搞出来的最小权值再做一次单调队列,更新答案
感觉很难讲清楚啊……看代码好了……虽然代码可能更不清楚……
//minamoto
#include
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
template
template
q[++t]=j;
if(q[h]<=j-B+D+) ++h;
mn[i][j]=sum2[i][q[h]];
}
}
}
void solve(){
for(int j=D+;j
q[++t]=i;
if(q[h]<=i-A+C+) ++h;
cmax(res,sum1[i+][j+]-mn[q[h]][j]);
}
}
}
int main(){
// freopen("testdata.in","r",stdin);
n=read(),m=read(),A=read(),B=read(),C=read(),D=read();
if(n==||m==) return puts(""),;
for(int i=;i<=n;++i) for(int j=;j<=m;++j)
sum[i][j]=read()+sum[i-][j]+sum[i][j-]-sum[i-][j-];
for(int i=A;i<=n;++i) for(int j=B;j<=m;++j)
sum1[i][j]=sum[i][j]-sum[i-A][j]-sum[i][j-B]+sum[i-A][j-B];
for(int i=C;i<=n;++i) for(int j=D;j<=m;++j)
sum2[i][j]=sum[i][j]-sum[i-C][j]-sum[i][j-D]+sum[i-C][j-D];
init(),solve();
printf("%d\n",res);
return ;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章