luogu 2219[HAOI2007]修筑绿化带 单调队列

Code:

#include<bits/stdc++.h>
using namespace std;
#define setIO(s) freopen(s".in","r",stdin)
#define maxn 1002
#define inf 1000000000
deque<int>q;
int n,m,A,B,C,D;
int minv[maxn][maxn],sumv[maxn][maxn],val[maxn][maxn],tot[maxn][maxn];
int main()
{
// setIO("input");
scanf("%d%d%d%d%d%d",&n,&m,&A,&B,&C,&D);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
scanf("%d",&sumv[i][j]);
sumv[i][j]+=(sumv[i][j-1]+sumv[i-1][j]-sumv[i-1][j-1]);
}
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
if(i>=A&&j>=B) tot[i][j]=sumv[i][j]-sumv[i-A][j]-sumv[i][j-B]+sumv[i-A][j-B];
if(i>=C&&j>=D) val[i][j]=sumv[i][j]-sumv[i-C][j]-sumv[i][j-D]+sumv[i-C][j-D];
}
}
for(int j=1;j<=m;++j)
{
while(!q.empty()) q.pop_front();
for(int i=2;i<=n;++i)
{
while(!q.empty()&&i-q.front()+1>=A-C) q.pop_front();
if(!val[i-1][j]) { minv[i][j]=inf; continue; }
while(!q.empty()&&val[i-1][j]<=val[q.back()][j]) q.pop_back();
q.push_back(i-1);
minv[i][j]=val[q.front()][j];
}
}
int ans=0;
for(int i=1;i<=n;++i)
{
while(!q.empty()) q.pop_front();
for(int j=2;j<=m;++j)
{
while(!q.empty()&&j-q.front()+1>=B-D) q.pop_front();
if(!val[i][j-1]) continue;
while(!q.empty()&&minv[i][j-1]<=minv[i][q.back()]) q.pop_back();
q.push_back(j-1);
ans=max(ans, tot[i][j]-minv[i][q.front()]);
}
}
printf("%d\n",ans);
return 0;
}

  

上一篇:Android -- PopupWindow(其中嵌套ListView 可以被点击)


下一篇:两数相加(二)