[APIO 2009 OIL]分类讨论

【算法分析】

这个要想想。。。

首先我们注意到，必然有一条竖线或者横线把3个矩形分成一边一个，一边两个的情况，于是预处理，然后再分类讨论即可。。。

【CODE】

#include #include #include const int N=1511;
int m,n,k;
int w[N][N],sum[N][N],lu1[N][N],rd1[N][N];
int ru1[N][N],ld1[N][N],lu2m[N],lu2n[N],rd21[N],rd22[N];

inline int max(int x,int y){
       if (x>y) return x;
       return y;
}

void input(){
     scanf("%d%d%d",&m,&n,&k);
     int i,j;
     for (i=1;i<=m;i++)
       for (j=1;j<=n;j++) scanf("%d",&w[i][j]);
     memset(rd21,200,sizeof(rd21));
     memset(lu2m,200,sizeof(lu2m));
     memset(rd22,200,sizeof(rd22));
     memset(lu2n,200,sizeof(lu2n));
     memset(lu1,200,sizeof(lu1));
     memset(rd1,200,sizeof(rd1));
     memset(ld1,200,sizeof(ld1));
     memset(ru1,200,sizeof(ru1));
}

void change(){
     int i,j;
     for (i=1;i<=m;i++)
       for (j=1;j<=n;j++)
         sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+w[i][j];
     m=m-k+1; n=n-k+1;
     for (i=1;i<=m;i++)
       for (j=1;j<=n;j++)
         w[i][j]=sum[i+k-1][j+k-1]-sum[i-1][j+k-1]-sum[i+k-1][j-1]+sum[i-1][j-1];
}

void init(){
     int i,j;
     for (i=1;i<=m;i++)
       for (j=1;j<=n;j++){
           lu1[i][j]=max(lu1[i-1][j],lu1[i][j-1]);
           lu1[i][j]=max(lu1[i][j],w[i][j]);
       }
     for (i=m;i>=1;i–)
       for (j=n;j>=1;j–){
           rd1[i][j]=max(rd1[i+1][j],rd1[i][j+1]);
           rd1[i][j]=max(rd1[i][j],w[i][j]);
       }
     for (i=1;i<=m;i++)
       for (j=n;j>=1;j–){
           ru1[i][j]=max(ru1[i-1][j],ru1[i][j+1]);
           ru1[i][j]=max(ru1[i][j],w[i][j]);
       }
     for (i=m;i>=1;i–)
       for (j=1;j<=n;j++){
           ld1[i][j]=max(ld1[i+1][j],ld1[i][j-1]);
           ld1[i][j]=max(ld1[i][j],w[i][j]);
       }
//处理lu
     for (j=1;j<=n;j++){
         int &t=lu2m[j];
         t=lu2m[j-1];
         for (i=1;i<=m;i++){
           if (i>k) t=max(t,lu1[i-k][j]+w[i][j]);
           if (j>k) t=max(t,lu1[m][j-k]+w[i][j]);
           if (i+k<=m) t=max(t,ld1[i+k][j]+w[i][j]);
         }
     }
     for (i=1;i<=m;i++){
         int &t=lu2n[i];
         t=lu2n[i-1];
         for (j=1;j<=n;j++){        
           if (j>k) t=max(t,lu1[i][j-k]+w[i][j]);
           if (i>k) t=max(t,lu1[i-k][n]+w[i][j]);
           if (j+k<=n) t=max(t,ru1[i][j+k]+w[i][j]);
         }
     }
//处理rd
     for (j=n;j>=1;j–){
         int &t=rd21[j];
         t=rd21[j+1];
         for (i=1;i<=m;i++){
             if (i>k) t=max(t,ru1[i-k][j]+w[i][j]);
             if (j+k<=n) t=max(t,rd1[1][j+k]+w[i][j]);
             if (i+k<=m) t=max(t,rd1[i+k][j]+w[i][j]);
         }
     }
     for (i=m;i>=1;i–){
         int &t=rd22[i];
         t=rd22[i+1];
         for (j=1;j<=n;j++){
             if (j+k<=n) t=max(t,rd1[i][j+k]+w[i][j]);
             if (i+k<=m) t=max(t,rd1[i+k][1]+w[i][j]);
             if (j>k) t=max(t,ld1[i][j-k]+w[i][j]);
         }
     }
}

void work(){
     int ans=0,i,j;
     for (i=1;i+k<=m;i++){
         ans=max(ans,lu1[i][n]+rd22[i+k]);
         ans=max(ans,lu2n[i]+rd1[i+k][1]);
     }
     for (j=1;j+k<=n;j++){
         ans=max(ans,lu1[m][j]+rd21[j+k]);
         ans=max(ans,lu2m[j]+rd1[1][j+k]);
     }
     printf("%dn",ans);
}

int main(){
    freopen("oil.in","r",stdin);
    freopen("oil.out","w",stdout);
    input();
    change();
    init();
    work();
}