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;

 

}