BZOJ1177: [Apio2009]Oil【分类讨论】

1177: [Apio2009]Oil

【题目描述】

传送门

【题解】

一道分类讨论的题目,将矩形分成三块,表示三个油田分别取在这三块中的最大值,一共有6中分法,对于其中四种可以直接算,对于两行或两列的情况,预处理中间的一行/列就可以了。

代码如下

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MAXN=1505;
int n,m,K;
LL Sum[MAXN][MAXN],F[4][MAXN][MAXN],H[MAXN],L[MAXN],Ans;
LL get(int x,int y){return Sum[x][y]-Sum[x-K][y]-Sum[x][y-K]+Sum[x-K][y-K];}
int main(){
    scanf("%d%d%d",&n,&m,&K);
    for(int i=1;i<=n;i++)
    for(int j=1,x;j<=m;j++) scanf("%d",&x),Sum[i][j]=Sum[i-1][j]+Sum[i][j-1]-Sum[i-1][j-1]+x;
    for(int i=K;i<=n;i++) for(int j=K;j<=m;j++) F[0][i][j]=max(F[0][i-1][j],max(F[0][i][j-1],get(i,j)));//左上 
    for(int i=n-K+1;i;i--) for(int j=K;j<=m;j++) F[1][i][j]=max(F[1][i+1][j],max(F[1][i][j-1],get(i+K-1,j)));//左下 
    for(int i=K;i<=n;i++) for(int j=m-K+1;j;j--) F[2][i][j]=max(F[2][i-1][j],max(F[2][i][j+1],get(i,j+K-1)));//右上 
    for(int i=n-K+1;i;i--) for(int j=m-K+1;j;j--) F[3][i][j]=max(F[3][i+1][j],max(F[3][i][j+1],get(i+K-1,j+K-1)));//右下 
    for(int i=K;i<=n;i++) for(int j=K;j<=m;j++) H[i]=max(H[i],get(i,j)),L[j]=max(L[j],get(i,j));
    for(int i=K;i<=n-K;i++) for(int j=K;j<=m-K;j++) Ans=max(Ans,F[0][i][m]+F[1][i+1][j]+F[3][i+1][j+1]);
    for(int i=K;i<=n-K;i++) for(int j=K;j<=m-K;j++) Ans=max(Ans,F[0][i][j]+F[1][i+1][m]+F[2][i][j+1]);
    for(int i=K;i<=n-K;i++) for(int j=K;j<=m-K;j++) Ans=max(Ans,F[0][n][j]+F[2][i][j+1]+F[3][i+1][j+1]);
    for(int i=K;i<=n-K;i++) for(int j=K;j<=m-K;j++) Ans=max(Ans,F[0][i][j]+F[1][i+1][j]+F[3][1][j+1]);
    for(int i=K;i<=n;i++) for(int j=i+K;j<=n-K;j++) Ans=max(Ans,F[0][i][m]+H[j]+F[1][j+1][m]);
    for(int i=K;i<=m;i++) for(int j=i+K;j<=m-K;j++) Ans=max(Ans,F[0][n][i]+L[j]+F[2][n][j+1]);
    printf("%lld\n",Ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部