P2219 [HAOI2007]修筑绿化带（二维单调队列）

 

 

 

题目描述

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

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

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

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

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

输入输出格式

输入格式：

 

第一行有6个正整数M,N,A,B,C,D

接下来一个M*N的数字矩阵，其中矩阵的第i行j列元素为一个整数Xij,表示该花园的第i行第j列的土地“肥沃度”。

 

输出格式：

 

一个正整数，表示绿化带的最大肥沃程度。

 

输入输出样例

输入样例#1： 复制

4 5 4 4 2 2 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

输出样例#1： 复制

132

说明

数据范围

30%的数据，1<=M,N<=50

100%的数据，1<=M,N<=1000,1<=A<=M,1<=B<=N,1<=C<=A-2,1<=D<=B-2，1<=“肥沃度”<=100 

 

 

 

---

 

---

 

 首先n**4暴力 枚举大矩形，在枚举里面可能存在的小矩形

优化： 发现枚举里面小矩形的步骤可以省略，因为我们每次枚举小矩形都是相对大矩形在一定范围内的，所以可以预处理出一定范围内的小矩形的最小值，这样的话直接枚举打矩形然后减去一定范围内的小矩形的最小值就行了，复杂度o（n**2)

预处理出所有小矩形的面积

此题是二维的，所以先处理的在行方向上固定列范围内的最小值，在此基础上处理行方向上一定范围的最小值

 

 

 

 

---

 

---

  

#include"bits/stdc++.h"
using namespace std;

int f[1005][1005];
int sum[1005][1005];

int f1[1005][1005];
int f2[1005][1005];
int f3[1005][1005];

int n,m,a,b,c,d;

int work(int x1,int y1,int x2,int y2)
{
    return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}

int main()
{
    cin>>n>>m>>a>>b>>c>>d;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            scanf("%d",&f[i][j]);
        }
     } 
     
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+f[i][j];
     } 
   
/*    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)cout<<sum[i][j]<<" ";cout<<endl;
    }*/
    
    for (int i=c+1;i<n;i++)
    {
        for (int j=1+d;j<=1+m;j++) f1[i][j]=sum[i][j]-sum[i-c][j]-sum[i][j-d]+sum[i-c][j-d]; 
    }
    
    deque<int> q;
    
    for (int i=c+1;i<n;i++)//这从c+1开始，是防止从花坛边上转移过来，下同。
    {
         while (!q.empty())q.pop_front();
         for (int j=d+1;j<m;j++)
         {
              while (!q.empty()&&q.front()+b-d-2+1-1<j)q.pop_front();
              while (!q.empty()&&f1[i][q.back()]>f1[i][j])q.pop_back();
              q.push_back(j);f2[i][j]=f1[i][q.front()];
         //     cout<<i<<": "<<q.size()<<endl;
         }
    }
    
    
    for (int j=d+1;j<m;j++)
    {
         while (!q.empty())q.pop_front();
         for (int i=c+1;i<n;i++)
        {
             while (!q.empty()&&q.front()+a-c-2+1-1<i)q.pop_front();
              while (!q.empty()&&f2[q.back()][j]>f2[i][j])q.pop_back();
              q.push_back(i);f3[i][j]=f2[q.front()][j];
              //cout<<j<<": "<<q.size()<<endl;
        }
    }
    
    
    
    
    /*    for (int i=c;i<=n;i++)
    {
    
         for (int j=d;j<=m;j++)
         {
              cout<<f3[i][j]<<" ";
         }
         cout<<endl;
    }*/
    
        int ans=0;
    for (int i=a;i<=n;i++)
    {
        for (int j=b;j<=m;j++)
        {
            ans=max(ans,work(i-a+1,j-b+1,i,j)-f3[i-1][j-1]);
        }
    }
    
    
    return cout<<ans,0;


}