状压DP例题-526互联

## [P2831愤怒的小鸟](https://www.luogu.com.cn/problem/P2831)

首先记录抛物线的方案。根据题意可知，两个点可能会确定一条符合题设的抛物线。所以$O(n^2)$枚举两个点，如果它们能够构成一个符合题设的抛物线，就再$O(n)$扫一遍，将这个抛物线能够到达的点记录下来，状态压缩记录成一种方案。别忘了只有抛物线只到达一个点也是一种方案。于是我们得到一个数组$s$，$s[i]$表示第$i$种方案的状态。

接下来是状压DP。设$f[i]$表示状态为$i$时的最小抛物线数量。枚举$s$中的每一个元素，另$f[i|s[j]]=min(f[i|s[j]],f[i]+1)$，答案是$f[(1<<n)-1]$

## [P2157学校食堂](https://www.luogu.com.cn/problem/P2157)

设 $f[i][j][k]$ 表示第 $1$ 个人到第 $i-1$ 个人已经打完饭，第 $i$ 个人以及后面七个人是否打饭的状态为 $j$ ，当前最后一个打饭的人编号为 $i+k$ .

如果第 $i$ 个人打好了饭（即 $j$&$1==true$ ），则状态转移方程为 $f[i+1][j>>1][k-1]=min(f[i+1][j>>1][k-1],f[i][j][k]).$

如果第 $i$ 个人还没有打好饭，我们可以枚举 $i$ 到 $i+7$ 的所有人，让他们先打饭。也就是枚举 $h=0...7$ ，状态转移方程为 $f[i][j|(1<<h)][h]=min(f[i][j|(1<<h)][h],f[i][j][k]+time(i+k,i+h)).$

需要注意的是 $k$ 的范围是 $[-8,0]$ ，写代码的时候要将 $k$ 整体加上 $8.$

初始化： $f[1][0][7]=0$，其余全部是正无穷

答案： $f[n+1][0][k](k∈[0,8])$