SDOI2009[学校食堂]

状态压缩DP。

f[i][STATE][BEFORE]表示i以前的都已经吃到饭了,然后STATE用二进制压缩表示后面8个人的吃饭情况,BEFORE表示最后一个吃饭的人是谁,可以用相对位置表示,于是-8<=BEFORE<=8。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-26

DESCRIPTION:

山东2009年省选 学校食堂

*/

#include <stdio.h>

#include <string.h>

 

const int oo=0x7f7f7f7f;

const int MAXN=1000+10;

const int MAXB=7+1;

const int MAXBEFORE=MAXB*2+1;

const int MAXSTATE=1<<(MAXB+1);

int C;

int N;

int t[MAXN],b[MAXN];

int f[MAXN][MAXSTATE][MAXBEFORE];

int BEFORE(int x)

{

    return x+MAXB;

}

int STATE(int x)

{

    return 1<<x;

}

int min(int a,int b)

{

    return a<b?a:b;

}

int cost(int a,int b)

{

    return a^b;

}

int get(int i,int before,int state,int ii,int bbefore,int sstate)

{

    int& A=f[i][state][BEFORE(before)];

    int B=f[ii][sstate][BEFORE(bbefore)];

    A=min(A,B+cost(t[ii+bbefore],t[i+before]));

}

int main()

{

    scanf(“%d”,&C);

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

    {

        scanf(“%d”,&N);

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

            scanf(“%d%d”,t+i,b+i);

        memset(f,oo,sizeof(f));

        for (int before=0;before<=MAXB;before++)

        {

            bool can_get=true;

            for (int k=0;k<MAXB;k++)

                if ((1+before)-(1+k)>b[1+k])

                {

                   can_get=false;

                   break;

                }

            if (can_get) f[1][STATE(before)][BEFORE(before)]=0;

        }

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

            for (int sstate=0;sstate<MAXSTATE;sstate++)

                for (int bbefore=-MAXB;bbefore<=MAXB;bbefore++)

                    if (f[ii][sstate][BEFORE(bbefore)]!=oo)

                       for (int todo=0;todo<=b[ii];todo++)

                       {

                           int i=ii,before=todo,state=sstate|STATE(todo);

                           bool can_get=true;

                           for (int k=0;k<MAXB;k++)

                               if (!(state&STATE(k))&&((i+todo)-(i+k))>b[i+k])

                               {

                                  can_get=false;

                                  break;

                               }

                           if (can_get)

                           {

                              int di=0;

                              while (di<=MAXB&&(state&STATE(di))) di++;

                              i+=di,before-=di,state>>=di;

                              get(i,before,state,ii,bbefore,sstate);

                           }

                       }

        int answer=oo;

        for (int before=-MAXB;before<=0;before++)

            if (answer>f[N+1][0][BEFORE(before)])

               answer=f[N+1][0][BEFORE(before)];

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

    }

}

 

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注