【APIO2009】采油区域 | Mrsrz's blog

分类讨论

题目大意：

给定一个 $n\times m$ 的图，每个格子有正整数权值。

现在要找 $3$ 块互不相交的 $k\times k$ 的区域，使得 $3$ 块区域的权值和最大。求这个最大的权值和。

题解：

选 $3$ 块的方案只有以下 $6$ 种。

我们对这 $6$ 种情况分类讨论即可。

最后两种可以递推。令 $f_{i,t}$ 表示当前选到第 $i$ 行（列），选了 $t$ 块的最大权值和。

剩下的 $4$ 种，我们分别求出每个左上角、右上角、左下角、右下角、左侧、右侧、上侧、下侧的最大值。然后对于每一种情况，我们枚举中间的交点，然后分为两个角落和一个侧面，可以直接计算。

计算一个矩形区域的和，通过二维前缀和预处理，做到 $O(1)$ 查询。

时间复杂度 $O(nm)$。

Code：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1555;
int n,m,k,a[N][N],pre[N][N],ans;
int LU[N][N],LD[N][N],RU[N][N],RD[N][N],L[N],R[N],U[N],D[N];
int P[N][4];
inline int calc(int r1,int c1,int r2,int c2){
    return pre[r2][c2]-pre[r1-1][c2]-pre[r2][c1-1]+pre[r1-1][c1-1];
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j){
        cin>>a[i][j];
        pre[i][j]=a[i][j]+pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1];
    }
    for(int i=k;i<=n;++i)
    for(int j=k;j<=m;++j)
    LU[i][j]=max({LU[i-1][j],LU[i][j-1],calc(i-k+1,j-k+1,i,j)});
    for(int i=n-k+1;i;--i)
    for(int j=k;j<=m;++j)
    LD[i][j]=max({LD[i+1][j],LD[i][j-1],calc(i,j-k+1,i+k-1,j)});
    for(int i=k;i<=n;++i)
    for(int j=m-k+1;j;--j)
    RU[i][j]=max({RU[i-1][j],RU[i][j+1],calc(i-k+1,j,i,j+k-1)});
    for(int i=n-k+1;i;--i)
    for(int j=m-k+1;j;--j)
    RD[i][j]=max({RD[i+1][j],RD[i][j+1],calc(i,j,i+k-1,j+k-1)});
    for(int j=1;j<=m;++j)
    L[j]=LU[n][j],R[j]=RU[n][j];
    for(int i=1;i<=n;++i)
    U[i]=LU[i][m],D[i]=LD[i][m];
    for(int i=k;i<=n-k+1;++i)
    for(int j=k;j<=m-k+1;++j)
    ans=max({ans,D[i]+LU[i-1][j]+RU[i-1][j+1],U[i]+LD[i+1][j]+RD[i+1][j+1],
    L[j]+RU[i][j+1]+RD[i+1][j+1],R[j]+LU[i][j-1]+LD[i+1][j-1]});
    memset(P,-1,sizeof P);
    P[0][0]=0;
    for(int j=1;j<=m;++j){
        P[j][0]=0;
        if(j>=k)
        for(int t=1;t<=3;++t){
            int&s=P[j][t];
            P[j][t]=P[j-1][t];
            if(P[j-k][t-1]>=0)
            for(int i=k;i<=n;++i)
            s=max(s,P[j-k][t-1]+calc(i-k+1,j-k+1,i,j));
        }
    }
    ans=max(ans,P[m][3]);
    memset(P,-1,sizeof P);
    P[0][0]=0;
    for(int i=1;i<=n;++i){
        P[i][0]=0;
        if(i>=k)
        for(int t=1;t<=3;++t){
            int&s=P[i][t];
            P[i][t]=P[i-1][t];
            if(P[i-k][t-1]>=0)
            for(int j=k;j<=m;++j)
            s=max(s,P[i-k][t-1]+calc(i-k+1,j-k+1,i,j));
        }
    }
    ans=max(ans,P[n][3]);
    cout<<ans<<endl;
    return 0;
}