注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

APIO2009[采油区域/oil]  

2010-04-17 15:06:40|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

用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种情况。如下图:

APIO2009[oil]解题报告 - 天之骄子 - 天之骄子的家

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

然后,可能会发现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];

}

 

  评论这张
 
阅读(972)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018