[动态规划][SDOI2009]学校食堂

####题目描述
小F 的学校在城市的一个偏僻角落，所有学生都只好在学校吃饭。学校有一个食堂，虽然简陋，但食堂大厨总能做出让同学们满意的菜肴。当然，不同的人口味也不一定相同，但每个人的口味都可以用一个非负整数表示。 由于人手不够，食堂每次只能为一个人做菜。做每道菜所需的时间是和前一道菜有关的，若前一道菜的对应的口味是a，这一道为b，则做这道菜所需的时间为（a or b）-（a and b），而做第一道菜是不需要计算时间的。其中，or 和and 表示整数逐位或运算及逐位与运算，C语言中对应的运算符为“|”和“&”。

学生数目相对于这个学校还是比较多的，吃饭做菜往往就会花去不少时间。因此，学校食堂偶尔会不按照大家的排队顺序做菜，以缩短总的进餐时间。

虽然同学们能够理解学校食堂的这种做法，不过每个同学还是有一定容忍度的。也就是说，队伍中的第i 个同学，最多允许紧跟他身后的Bi 个人先拿到饭菜。一旦在此之后的任意同学比当前同学先拿到饭，当前同学将会十分愤怒。因此，食堂做菜还得照顾到同学们的情绪。 现在，小F 想知道在满足所有人的容忍度这一前提下，自己的学校食堂做完这些菜最少需要多少时间。

####输入格式：
第一行包含一个正整数C，表示测试点的数据组数。 每组数据的第一行包含一个正整数N，表示同学数。 每组数据的第二行起共N行，每行包含两个用空格分隔的非负整数Ti和Bi，表示按队伍顺序从前往后的每个同学所需的菜的口味和这个同学的忍受度。 每组数据之间没有多余空行。

####输出格式：
包含C行，每行一个整数，表示对应数据中食堂完成所有菜所需的最少时间.

----------
###题解:
状压啊,然而只想出状态,只好借鉴一下其他dalao的博客了qwq

$f[i][s][k]$表示讨论到第$i$个人,他后面(包括他自己)的人拿没拿到饭的状态是$s$,并且前一个拿饭的人是$k$的最小代价.
不难发现对于一个人 $x$ 上一个拿饭的人只会在 $[x-7,x+7]$ 这个区间里,所以第三维状态可以变成前一个拿饭的人相对于 $i$ 来说位置在 $k$ ,$-7\leq k\leq7$
其实转移并不难,如果当前 $s\&1==1$,表示第i个人自己已经拿到饭了,就可一开始讨论下一个人,也就是$$f[i+1][s>>1][k-1]=min(f[i+1][s>>1][k-1],f[i][s][k])$$
$s>>1$ 其实就是 $i+1$ 的状态.
因为位置变化了1, $k$ 存的是相对位置,所以要对应的将 $k-1$.

然后可以枚举下一个不在当前 $s$ 中的人 $nx$ ,表示下一个拿饭的人是 $nx$(也是相对位置) ,注意这个 $nx$ 不能超过任何一个未拿饭的人的忍耐限制.
我们就有转移:
$$f[i][j|(1<<nx)][nx]=min(f[i][j|(1<<nx)][nx],f[i][j][k]+get(i+k,i+nx));$$
$get(a,b)$ 表示先选 $a$ 再选 $b$ 的价值.

对于最后一维的负数的处理,只需要整体偏移一下即可.

----------
贴上代码:
```
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define Z 7
#define inf 1999999999
using namespace std;
int f[1005][257][15];
int t[1005],b[1005],n,F=(1<<8)-1;
inline int get(int a,int b){return a?(t[a]^t[b]):0;}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d%d",&t[i],&b[i]);
		for(int i=1;i<=n;i++)
			for(int j=0;j<=F;j++)
				for(int k=-7;k<=7;k++)
					f[i][j][k+Z]=inf;
		f[1][0][Z-1]=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<=F;j++)
			{
				for(int k=-7;k<=7;k++)
				{
					if(f[i][j][k+Z]==inf) continue;
					if(j&1) {f[i+1][j>>1][k-1+Z]=min(f[i+1][j>>1][k-1+Z],f[i][j][k+Z]);}
					int lim=inf;
					for(int nx=0;nx<=7;nx++)
					{
						if(!((j>>nx)&1))
						{
							if(nx>lim) break;
							lim=min(lim,b[i+nx]+nx);
							f[i][j|(1<<nx)][nx+Z]=min(f[i][j|(1<<nx)][nx+Z],f[i][j][k+Z]+get(i+k,i+nx));							
						}
					}
				}
			}
		}
		int ans=inf;
		for(int i=0;i<=14;i++) ans=min(ans,f[n][1][i]);
		printf("%d\n",ans);		
	}
}
```

PhantasmDragon 's Blog