状态压缩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);
}
}