APIO2009[采油区域/oil]

用g[i][j]表示以(i,j)和(i-K+1,j-K+1)为两个顶点的正方形的价值，然后递推求之。

f1_1[i][j]表示以(1,1)和(i,j)为两个顶点的矩形内最大的K*K的方形的价值，递推求之。f1_N,fM_1,fM_N用相似的方法弄出来。

然后，进入主要的部分，分情况。因为我们需要三个方块，其实就是将油区整个分为3份，然后每份里找一个方块。不难发现，一共只有6种情况。如下图：

然后，利用先前的预处理，加上枚举分割线，就可以得出结果了。

然后，可能会发现TLE，这可能是因为读文件太慢了，可以自己用底层函数重写输入语句。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-17

DESCRIPTION:

$DESCRIPTION

*/

#include <stdio.h>

 

#define MAXM 1500

#define MAXN 1500

#define MAX(a,b) ((a)>(b)?(a):(b))

#define update(who,with) if ((who)<(with)) {(who)=(with);}

 

int M,N,K;

int map[MAXM][MAXN];

 

int f[MAXM][MAXN];

int g[MAXM][MAXN];

int maxx[MAXM];

int maxy[MAXN];

int max[MAX(MAXM,MAXN)];

int f1_1[MAXM][MAXN];

int f1_N[MAXM][MAXN];

int fM_1[MAXM][MAXN];

int fM_N[MAXM][MAXN];

 

int answer;

 

void update_case1234(int,int);

void update_case5();

void update_case6();

 

bool isNumber[256];

void read(int& who)

{

    char get;

    who=0;

    while (isNumber[get=getchar()]) who=who*10+get-‘0’;

}

 

int main()

{

    //freopen(“oil.in”,”r”,stdin);

    //freopen(“oil.out”,”w”,stdout);

    isNumber[‘0’]

    =isNumber[‘1’]

    =isNumber[‘2’]

    =isNumber[‘3’]

    =isNumber[‘4’]

    =isNumber[‘5’]

    =isNumber[‘6’]

    =isNumber[‘7’]

    =isNumber[‘8’]

    =isNumber[‘9’]

    =true;

    read(M);

    read(N);

    read(K);//scanf(“%d %d %d\n”,&M,&N,&K);

    for (int i=0;i<M;i++)

        for (int j=0;j<N;j++)

        {

            //scanf(“%d”,&map[i][j]);

            //if (j+1==N) scanf(“\n”);

            //else scanf(” “);

            read(map[i][j]);

        }

    for (int i=0;i<M;i++)

        for (int j=0;j<N;j++)

        {

            if (j>=K)

                f[i][j]=f[i][j-1]+map[i][j]-map[i][j-K];

            else if (j>0)

                f[i][j]=f[i][j-1]+map[i][j];

            else

                f[i][j]=map[i][j];

            //printf(“f[%d][%d]=%d\n”,i+1,j+1,f[i][j]);

            if (i>=K)

                g[i][j]=g[i-1][j]+f[i][j]-f[i-K][j];

            else if (i>0)

                g[i][j]=g[i-1][j]+f[i][j];

            else

                g[i][j]=f[i][j];

            //printf(“g[%d][%d]=%d\n”,i+1,j+1,g[i][j]);

            if (maxx[i]<g[i][j]) maxx[i]=g[i][j];

            if (maxy[j]<g[i][j]) maxy[j]=g[i][j];

        }

    //for (int i=0;i<M;i++) printf(“maxx[%d]=%d\n”,i+1,maxx[i]);

    //for (int j=0;j<N;j++) printf(“maxy[%d]=%d\n”,j+1,maxy[j]);

    for (int i=K-1;i<M;i++)

        for (int j=K-1;j<N;j++)

        {

            f1_1[i][j]=g[i][j];

            if (i>0) update(f1_1[i][j],f1_1[i-1][j]);

            if (j>0) update(f1_1[i][j],f1_1[i][j-1]);

            //printf(“f1_1[%d][%d]=%d\n”,i+1,j+1,f1_1[i][j]);

        }

    for (int i=K-1;i<M;i++)

        for (int j=N-K;j>=0;j–)

        {

            f1_N[i][j]=g[i][j+K-1];

            if (i>0) update(f1_N[i][j],f1_N[i-1][j]);

            if (j<N-1) update(f1_N[i][j],f1_N[i][j+1]);

            //printf(“f1_N[%d][%d]=%d\n”,i+1,j+1,f1_N[i][j]);

        }

    for (int i=M-K;i>=0;i–)

        for (int j=K-1;j<N;j++)

        {

            fM_1[i][j]=g[i+K-1][j];

            if (i<M-1) update(fM_1[i][j],fM_1[i+1][j]);

            if (j>0) update(fM_1[i][j],fM_1[i][j-1]);

            //printf(“fM_1[%d][%d]=%d\n”,i+1,j+1,fM_1[i][j]);

        }

    for (int i=M-K;i>=0;i–)

        for (int j=N-K;j>=0;j–)

        {

            fM_N[i][j]=g[i+K-1][j+K-1];

            if (i<M-1) update(fM_N[i][j],fM_N[i+1][j]);

            if (j<N-1) update(fM_N[i][j],fM_N[i][j+1]);

            //printf(“fM_N[%d][%d]=%d\n”,i+1,j+1,fM_N[i][j]);

        }

 

    //CASE 1 2 3 4

    for (int i=K-1;i<=M-K;i++)

        for (int j=K-1;j<=N-K;j++)

            update_case1234(i,j);

    //CASE 5

    update_case5();

    //CASE 6

    update_case6();

    printf(“%d\n”,answer);

    //fclose(stdin);

    //fclose(stdout);

    return 0;

}

 

void update_case1234(int a,int b)

{

    //CASE 1

    if (a<M-1&&b<N-1)

        update(answer,f1_1[a][b]+f1_N[a][b+1]+fM_N[a+1][0]);

    //CASE 2

    if (a>0&&b<N-1)

        update(answer,fM_1[a][b]+fM_N[a][b+1]+f1_N[a-1][0]);

    //CASE 3

    if (a<M-1&&b<N-1)

        update(answer,f1_1[a][b]+fM_1[a+1][b]+fM_N[0][b+1]);

    //CASE 4

    if (a<M-1&&b>0)

        update(answer,f1_N[a][b]+fM_N[a+1][b]+fM_1[0][b-1]);

}

void update_case5()

{

    static int maxx3[4][MAXM];

    for (int k=1;k<=3;k++)

        for (int i=K-1;i<M;i++)

            if (i>=K&&maxx3[k][i-1]<maxx3[k-1][i-K]+maxx[i])

                maxx3[k][i]=maxx3[k-1][i-K]+maxx[i];

            else if (i<K&&maxx3[k][i-1]<maxx[i])

                maxx3[k][i]=maxx[i];

            else

                maxx3[k][i]=maxx3[k][i-1];

    //printf(“case5=%d\n”,maxx3[3][M-1]);

    if (answer<maxx3[3][M-1]) answer=maxx3[3][M-1];

}

void update_case6()

{

    static int maxy3[4][MAXN];

    for (int k=1;k<=3;k++)

        for (int i=K-1;i<N;i++)

            if (i>=K&&maxy3[k][i-1]<maxy3[k-1][i-K]+maxy[i])

                maxy3[k][i]=maxy3[k-1][i-K]+maxy[i];

            else if (i<K&&maxy3[k][i-1]<maxy[i])

                maxy3[k][i]=maxy[i];

            else

                maxy3[k][i]=maxy3[k][i-1];

    //printf(“case6=%d\n”,maxy3[3][N-1]);

    if (answer<maxy3[3][N-1]) answer=maxy3[3][N-1];

}