HAOI 2007 修築綠化帶

首先求出每個AB的矩陣的數值和，以及每個CD的矩陣的數值和，用遞推的方法可以達到O(NM)。接下來，求出每個(A-2)(B-2)範圍內最小的CD的矩陣（因爲花壇不能建在綠化帶邊緣），可以用單調隊列的方法遞推，時間複雜度爲O(NM)。最後對於每個AB的侷限，求出其範圍內最小的花壇，時間複雜度爲O(NM)，總的時間複雜度就是O(N*M)。

這道題本身不難，關鍵在仔細處理好遞推的邊界。

/* 
 * Problem: HAOI2007 parterre
 * Author: Guo Jiabao
 * Time: 2009.4.20 10:32
 * State: Solved
 * Memo: 動態規劃 單調隊列 矩陣壓縮
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=1001;
using namespace std;
struct MonoQueue
{
    struct MQElement
    {
        int id,value;
    }Q[MAXN];
    int head,tail;
    void clear(){head=0;tail=-1;}
    void ins(int value,int id)
    {
        while(tail>=head && value<Q[tail].value) tail--;
        Q[++tail].value=value;
        Q[tail].id=id;
    }
    int getmin(int id)
    {
        while (Q[head].id<id) head++;
        return Q[head].value;
    }
}MQ;
struct Matrix
{
    int N,M;
    int X[MAXN][MAXN];
}Green,Flower,FM;
int N,M,A,B,C,D,EN,EM,Ans=0;
int X[MAXN][MAXN],Y[MAXN][MAXN];
void init()
{
    int i,j;
    freopen("parterre.in","r",stdin);
    freopen("parterre.out","w",stdout);
    scanf("%d%d%d%d%d%d",&N,&M,&A,&B,&C,&D);
    for (i=1;i<=N;i++)
        for (j=1;j<=M;j++)
            scanf("%d",&X[i][j]);
}
void solve()
{
    int i,j;
    Green.N=N+1-A; Green.M=M+1-B;
    Flower.N=N+1-C; Flower.M=M+1-D;
    EN=A-2-C+1; EM=B-2-D+1;
    FM.N=Flower.N+1-EN; FM.M=Flower.M+1-EM;
    for (j=1;j<=M;j++)
    {
        Y[1][j]=0;
        for (i=1;i<=A;i++)
            Y[1][j]+=X[i][j];
        for (i=2;i+A-1<=N;i++)
            Y[i][j]=Y[i-1][j]-X[i-1][j]+X[i+A-1][j];
    }

    for (i=1;i<=Green.N;i++)
    {
        Green.X[i][1]=0;
        for (j=1;j<=B;j++)
            Green.X[i][1]+=Y[i][j];
        for (j=2;j<=Green.M;j++)
            Green.X[i][j]=Green.X[i][j-1]-Y[i][j-1]+Y[i][j+B-1];
    }
    for (j=1;j<=M;j++)
    {
        Y[1][j]=0;
        for (i=1;i<=C;i++)
            Y[1][j]+=X[i][j];
        for (i=2;i+C-1<=N;i++)
            Y[i][j]=Y[i-1][j]-X[i-1][j]+X[i+C-1][j];
    }

    for (i=1;i<=Flower.N;i++)
    {
        Flower.X[i][1]=0;
        for (j=1;j<=D;j++)
            Flower.X[i][1]+=Y[i][j];
        for (j=2;j<=Flower.M;j++)
            Flower.X[i][j]=Flower.X[i][j-1]-Y[i][j-1]+Y[i][j+D-1];
    }
    for (j=1;j<=Flower.M;j++)
    {
        MQ.clear();
        for (i=1;i<=EN-1;i++)
            MQ.ins(Flower.X[i][j],i);
        for (i=1;i<=FM.N;i++)
        {
            MQ.ins(Flower.X[i+EN-1][j],i+EN-1);
            Y[i][j]=MQ.getmin(i);
        }
    }
    for (i=1;i<=FM.N;i++)
    {
        MQ.clear();
        for (j=1;j<=EM-1;j++)
            MQ.ins(Y[i][j],j);
        for (j=1;j<=FM.M;j++)
        {
            MQ.ins(Y[i][j+EM-1],j+EM-1);
            FM.X[i][j]=MQ.getmin(j);
        }
    }
    for (i=1;i<=Green.N;i++)
    {
        for (j=1;j<=Green.M;j++)
        {
            int R=Green.X[i][j];
            R-=FM.X[i+1][j+1];
            if (R>Ans)
                Ans=R;
        }
    }
}
int main()
{
    init();
    solve();
    printf("%dn",Ans);
    return 0;
}

<div class="MainText">

<a href="http://www.ruvtex.cn/cogs/problem/pdetail.php?pid=24" target="_blank">http://www.ruvtex.cn/cogs/problem/pdetail.php?pid=24</a>

<strong>修築綠化帶</strong>

<strong>【問題描述】</strong>

爲了增添公園的景緻，現在需要在公園中修築一個花壇，同時在畫壇四周修建一片綠化帶，讓花壇被綠化帶圍起來。
如果把公園看成一個M*N的矩形，那麼花壇可以看成一個C*D的矩形，綠化帶和花壇一起可以看成一個A*B的矩形。
如果將花園中的每一塊土地的“肥沃度”定義爲該塊土地上每一個小塊肥沃度之和，那麼，
綠化帶的肥沃度=A*B塊的肥沃度-C*D塊的肥沃度
爲了使得綠化帶的生長得旺盛，我們希望綠化帶的肥沃度最大。

<strong>【輸入】</strong>:

第一行有6個正整數M,N,A,B,C,D
接下來一個M*N的數字矩陣，其中矩陣的第i行j列元素爲一個整數Xij,表示該花園的第i行第j列的土地“肥沃度”。

<strong>【輸出】</strong>:

一個正整數，表示綠化帶的最大肥沃程度。

<strong>【輸入輸出樣例】</strong>
<strong>parterre.in </strong>
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

<strong>parterre.out </strong>
132

<strong>【數據範圍】</strong>

30%的數據，1&lt;=M,N&lt;=50
100%的數據，1&lt;=M,N&lt;=1000,1&lt;=A&lt;=M,1&lt;=B&lt;=N,1&lt;=C&lt;=A-2,1&lt;=D&lt;=B-2，1&lt;=“肥沃度”&lt;=100</div>

相關日誌