APIO2007[动物园/zoo]

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

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

用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;

 

}