题解 P3625 【[APIO2009]采油区域】

· · 题解

首先声明一下，排的数量此题解和我的代码中记作N，列记作M，与题目相反。

首先，一定可以划出一条直线（而且一定划在整数位置，竖线的话横坐标为整数，横线的话纵坐标为整数），把整个M\times N大矩形分为两个小矩形：一部分里只有一个完整的选中的K\times K正方形，另一部分里有完整的两个。这个东西很好证明，于是作为读者习题。

显然的，两个矩形的情况当然也可以完整分开。于是三个矩形的分布只能如图所示，其中每个正方形显然都是所在区域贡献最大的正方形。

只有两条分割线，可以O(NM)枚举。但是这要求查询贡献必须是O(1)，得提前算好。

那么，这就是一个在矩形区域里选择一个贡献最大的K\times K正方形的问题了。我们考虑计算数组ne[][],se[][],sw[][],nw[][]，即以某个方块为顶点的右上↗矩形，右下↘矩形，左下↙矩形，左上↖矩形中贡献最大的K\times K正方形的贡献（矩形里包括那个顶点方块本身）；和计算数组hen[][],shu[][]表示从第i排到第j排的横条的最大贡献和从第i列到第j列的竖条的最大贡献（包括i排（列）和j排（列））。

二维的区域和，瞬间想到二维前缀和，构建数组s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]。于是在O(NM)复杂度下可以把以某方格为顶点的四个方向的K\times K矩形的贡献计算出来。虽然实际上我们算一个方向就行了，因为比如(i,j)的右下正方形就是(i+k-1,j+k-1)的左上正方形。本人代码里选择左上角，记作k[][]。

如下图是一个以红方格为顶点的右上正方形。

还是考虑二维前缀和思想，我们以nw[][]数组为例。

如图，(i,j)的左上矩形中任何K\times K的正方形要么在淡蓝正方形中，要么在深蓝正方形中，要么都在，要么就是(i,j)的左上K\times K正方形。

于是容易写出：

nw[i][j]=max(nw[i-1][j],nw[i][j-1],\text{(i,j)的左上}K\times K\text{正方形的贡献})

大家会发现既在淡蓝矩形又在深蓝矩形的正方形统计了两遍，然而反正是取最大值所以完全没有问题。

如此，前四个数组很好搞出，接下来是剩下的两个。我们以hen[][]为例。

对于hen[i][i+K-1]，非常显然它就是max(k[i+K-1][j])\quad (j\in[K,M])。

对于其他的情况hen[i][j]，直接区间DP：

hen[i][j]=max(hen[i+1][j],hen[i][j-1])

然后直接开始统计即可~下面是代码。

虽然看着有点恶心，但思路非常清晰。

调不出来的话再回顾一下上面的思路吧。

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

int N,M,K;  //个人习惯，N才表示行
int s[1505][1505],k[1505][1505]; 
int ne[1505][1505],se[1505][1505],sw[1505][1505],nw[1505][1505];
int hen[1505][1505],shu[1505][1505];
int ANS;

int main(){
    cin>>N>>M>>K;
    for(int i=1;i<=N;i++)
    for(int j=1;j<=M;j++){
        int a;cin>>a;  //懒得设a数组了 
        s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a;
    }

    for(int i=K;i<=N;i++)  //左上K*K正方形 
    for(int j=K;j<=M;j++){
        k[i][j]=s[i][j]-s[i-K][j]-s[i][j-K]+s[i-K][j-K];
    }

    for(int i=K;i<=N;i++)  //nw,sw,se,ne 
    for(int j=K;j<=M;j++)
        nw[i][j]=max(nw[i-1][j],max(nw[i][j-1],k[i][j]));
    for(int i=N-K+1;i>=1;i--)
    for(int j=K;j<=M;j++)
        sw[i][j]=max(sw[i+1][j],max(sw[i][j-1],k[i+K-1][j]));
    for(int i=N-K+1;i>=1;i--)
    for(int j=M-K+1;j>=1;j--)
        se[i][j]=max(se[i+1][j],max(se[i][j+1],k[i+K-1][j+K-1]));
    for(int i=K;i<=N;i++)
    for(int j=M-K+1;j>=1;j--)
        ne[i][j]=max(ne[i-1][j],max(ne[i][j+1],k[i][j+K-1]));

    for(int i=1;i<=N-K+1;i++) //横排 
    for(int j=K;j<=M;j++)
        hen[i][i+K-1]=max(hen[i][i+K-1],k[i+K-1][j]);
    for(int len=K+1;len<=N;len++)
    for(int i=1;i<=N-len+1;i++)
        hen[i][i+len-1]=max(hen[i+1][i+len-1],hen[i][i+len-2]);

    for(int j=1;j<=M-K+1;j++) //竖列 
    for(int i=K;i<=N;i++)
        shu[j][j+K-1]=max(shu[j][j+K-1],k[i][j+K-1]);
    for(int len=K+1;len<=M;len++)
    for(int j=1;j<=M-len+1;j++)
        shu[j][j+len-1]=max(shu[j+1][j+len-1],shu[j][j+len-2]);

    for(int x1=K;x1<=N-K;x1++)  //统计,注意区域间千万不能有相交! 
    for(int x2=K;x2<=M-K;x2++){
        ANS=max(ANS,shu[1][x2]+ne[x1][x2+1]+se[x1+1][x2+1]); //图1 
        ANS=max(ANS,shu[x2+1][M]+nw[x1][x2]+sw[x1+1][x2]);   //图3
        ANS=max(ANS,hen[x1+1][M]+nw[x1][x2]+ne[x1][x2+1]);   //图4
        ANS=max(ANS,hen[1][x1]+sw[x1+1][x2]+se[x1][x2+1]);   //图6 
    }
    for(int x1=K;x1<=N-2*K;x1++)  //图2 
    for(int x2=x1+K;x2<=N-K;x2++)
        ANS=max(ANS,hen[1][x1]+hen[x1+1][x2]+hen[x2+1][N]);
    for(int x1=K;x1<=M-2*K;x1++)  //图4 
    for(int x2=x1+K;x2<=M-K;x2++)
        ANS=max(ANS,shu[1][x1]+shu[x1+1][x2]+shu[x2+1][N]);

    cout<<ANS;
}