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

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

APIO2007[动物园/zoo]  

2010-04-19 17:45:56|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

先将小朋友和围栏变成链,具体做法是找个地方切开圈,然后因为是切开的,这里的状态要枚举。

然后做动态规划,可以用二进制数储存状态,当然,也可以不用。

用f[k][state]表示推到k位置且k位置的状态为state时的最优值,那么f[k][state]=MAX(f[k-1][pre_state])+inc。

然后解释一下state,这是一个二进制数,a[4]a[3]a[2]a[1]a[0](a[i]=0或1),那么a[i]表示k+i位的动物是否被移走,1就移走,0就留下。

然后解释一下pre_state,pre_state可以推到state,即,若state=abcde,则pre_state=bcde0或bcde0。

然后解释一下inc,inc是increase的缩写,中文意思是增加,英文意思是increase。然后inc=看到的起始点为k并且被满足的孩子数。

然后,一步一步的推。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-19

DESCRIPTION:

$DESCRIPTION

*/

#include <stdio.h>

#include <string.h>

#include <time.h>

 

#define SIGHT 5

#define MAXC 50000

#define MAXN 10000

#define MAXK 2

#define K(k) ((k)%MAXK)

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

#define print(state,string)\

              printf("%s%d%d%d%d%d",\

              string,\

              (((state)&(1<<4))>>4),\

              (((state)&(1<<3))>>3),\

              (((state)&(1<<2))>>2),\

              (((state)&(1<<1))>>1),\

              (((state)&(1<<0))>>0));

 

typedef unsigned bit;

struct Child{int pos;bit love,hate;};

 

int N,C;

Child children[MAXC];

int f[MAXK][1<<(SIGHT)];

int answer;

 

int main()

{

    //freopen("zoo.in","r",stdin);

    //freopen("zoo.out","w",stdout);

   

    scanf("%d %d\n",&N,&C);

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

    {

        scanf("%d ",&children[i].pos);

        int love,hate;

        scanf("%d %d",&love,&hate);

        int pos;

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

        {

            scanf(" %d",&pos);

            if (pos<children[i].pos) pos+=N;

            children[i].love|=(1<<(pos-children[i].pos));

        }

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

        {

            scanf(" %d",&pos);

            if (pos<children[i].pos) pos+=N;

            children[i].hate|=(1<<(pos-children[i].pos));

        }

        scanf("\n");

        //printf("child%d's data:\npos:%d\n",i+1,children[i].pos);

        //print(children[i].love,"love:");printf("\n");

        //print(children[i].hate,"hate:");printf("\n");

    }

   

    for (int _start=0;_start<(1<<(SIGHT-1));_start++)

    {

        int start=_start<<1;

        memset(f,0xf0,sizeof(f));

        f[K(0)][start]=0;

        int begin=0,end=-1;

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

        {

            while (children[begin].pos<k&&begin<C) begin++;

            end=begin;

            while (children[++end].pos==k) ;

            for (int state=0;state<(1<<(SIGHT));state++)

            {

                int inc=0;

                if (children[begin].pos==k)

                   for (int j=begin;j<end;j++)

                       if ((children[j].love&state)||(children[j].hate&(~state)))

                          inc++;

                  

                f[K(k)][state]=MAX(f[K(k-1)][(state<<1)&((1<<(SIGHT))-1)],

                                   f[K(k-1)][((state<<1)|1)&((1<<(SIGHT))-1)])

                               +inc;

            }

        }

        answer=MAX(f[K(N+1)][start>>1],answer);

    }

   

    printf("%d\n",answer);

    //printf("runing time:%d\n",clock());

    //fclose(stdin);

    //fclose(stdout);

    return 0;

 

}

 

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

历史上的今天

评论

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

页脚

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