为了增添公园的景致，现在需要在公园中修筑一个花坛，同时在画坛四周修建一片绿化带，让花坛被绿化带围起来。

如果把公园看成一个M*N的矩形，那么花坛可以看成一个C*D的矩形，绿化带和花坛一起可以看成一个A*B的矩形。

如果将花园中的每一块土地的“肥沃度”定义为该块土地上每一个小块肥沃度之和，那么，

绿化带的肥沃度=A*B块的肥沃度-C*D块的肥沃度

为了使得绿化带的生长得旺盛，我们希望绿化带的肥沃度最大。

参考：

我们先预处理出每个A*B块的肥沃度，然后定义re[i][j]表示以(i,j)为右下角的点的A*B块当中的C*D块最小的肥沃度为多少。

显然后者可以单调队列优化，优化细节基本同。

PS：注意两个矩形不能有公共边，因此我才把更新值放在了中间（因为你新加进来的显然不能用）。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std; const int N=1e3+5; inline int read(){ int X=0,w=0;char ch=0; while(ch<'0'||ch>'9'){w|=ch=='-';ch=getchar();} while(ch>='0'&&ch<='9')X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } int a,b,c,d,n,m; int g[N][N],f[N][N],t[N][N]; int re[N][N],tmp[N][N],q[N][2]; void solve(){ for(int i=a;i<=m;i++){ for(int j=b;j<=n;j++){ f[i][j]=t[i][j]-t[i-a][j]-t[i][j-b]+t[i-a][j-b]; } } for(int i=c;i<=m;i++){ for(int j=d;j<=n;j++){ g[i][j]=t[i][j]-t[i-c][j]-t[i][j-d]+t[i-c][j-d]; } } memset(tmp,127/2,sizeof(tmp)); memset(re,127/2,sizeof(re)); for(int i=c;i<=m;i++){ int l=0,r=0; for(int j=d;j<=n;j++){ while(l
          
           =b-d)l++; if(l
           
            =g[i][j])r--; q[r][0]=g[i][j];q[r++][1]=j; } } for(int j=d;j<=n;j++){ int l=0,r=0; for(int i=c;i<=m;i++){ while(l
            
             =a-c)l++; if(l
             
              =tmp[i][j])r--; q[r][0]=tmp[i][j];q[r++][1]=i; } } } int main(){ m=read(),n=read(); a=read(),b=read(),c=read(),d=read(); for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ t[i][j]=t[i-1][j]+t[i][j-1]-t[i-1][j-1]+read(); } } solve(); int ans=0; for(int i=a;i<=m;i++){ for(int j=b;j<=n;j++){ ans=max(ans,f[i][j]-re[i][j]); } } printf("%d\n",ans); return 0; }
             
            
           
          
         
        
       
      
     

+++++++++++++++++++++++++++++++++++++++++++

 +本文作者：luyouqi233。 　　　　　　　　　　　　　　+

 +欢迎访问我的博客：+

+++++++++++++++++++++++++++++++++++++++++++