动态更新中

P2704 [NOI2001] 炮兵阵地

非常经典的一道状压dp入门题（但是2001年考的状压这么简单嘛

首先我们就考虑数据范围：m<=10，显然可以想到状压

我们把每一行的状态压到一个整数里，并且我们会发现我们每一次都只会用到前两行的东西

那么，我们在美剧当前这一行的时候就可以去枚举上面的两行，但是其实。。。这个东西看上去会爆炸

因为复杂度似乎是 $100*2^{30}$ 级别的，但是我们仔细想一想会发现，其实并不会使这么大的复杂度，因为每一行满足条件的状态并不多（最多100个

我们考虑在判断上一行和上两行和当前行有没有可以相互达到的地方的时候，我们可以用逻辑与运算

判断当前这一行有没有不合法的时候，就让当前行左移2位和原来的状态进行判断，左移一位再判断

[P1879 USACO06NOV]Corn Fields G

这个题就是上一个题简化了之后，在变成求方案数而已，上面的是两行，这个题是一行，就和上面一样转移就可以了

[P1896 SCOI2005]互不侵犯

这也就是个套路题嘛

我们考虑上一行和这一行的状态，就像上面的两道题一样

然后，上一行自身作比较，当前行自身作比较

上一行和当前行作比较的时候，直接与一下，左移与一下，右移与一下（必须左移右移都有

就可以了

[P3092 USACO13NOV]No Change G

这个题挺好

我们看到数据范围之后还是考虑压缩状态，把已经用过的钱压缩到一个状态里

然后我们考虑：现在已经用过了几个硬币，那么我们一定是要有先后顺序的

那么我们就从先后顺序来考虑

考虑枚举最后用的是那个硬币，然后用预处理出来的一个数组，记录这个硬币从上个状态最多可以买到那个状态进行转移

P3694 邦邦的大合唱站队

（不愧是kkk出的题

我们看到偶像团队的个数比较小，那么我们就考虑将团队压缩到状态里面去

假设说我们当前这个团队要全部塞到这个序列里

这个团队的人有一个总数len

那么我们就可以统计已经塞到序列里的其他团队，他们的人数总和r

那么当前团队一定是要塞到r+1~r+len这个区间的

那么就说明我们这个区间里当前团队的人并不需要出列，其他人需要

然后统计代价就可以了

P2167 [SDOI2009]Bill的挑战

这个题还挺好的，我是用的容斥（不过枚举子集的时候和状压有点异曲同工之妙

我们考虑，如果说现在要求只有k个的应该怎么办

先是求出来至少k个，然后容斥

容斥的时候系数就是 ${-1}^{now-k}*C(now,k)$

now是现在这个状态有多少个条件是满足的

为什么后面是组合数呢

我们发现，如果说这个串是要被重复搞得，那么他一定是被当前这个k个所多次选过的，组合数一下（意会即可）

P2157 [SDOI2009]学校食堂

挺难的。。。

（为什么SDOI2009三道状压啊。。。

这个题还是有一点点半懂半不懂得

我们对于每一个人来说，都只有那么几个人是可以窜到他前面的

并且这个人数还很小

那么我们就可以考虑一下状压把这些窜到他前面的人状态压缩一下

我们设f数组， $f[i][j][k]$ 表示，当前正在考虑第i个人，前i-1个人都已经打上饭了，这个人后面几个人（包括自己）的状态是j，当前打饭的是k

那么我们就可以去考虑一下，如果说当前的j是奇数，就可以直接向后转移（反正我现在打完饭了之后就已经可以转移到下一个阶段了

如果是偶数，我就可以从当前这个人的后面一部分人选出来一个人进行打饭的操作，然后转移到他（后面再转移第二个人第三个人等等

如果把这个人选上了，就要把状态进行改变，改变了状态之后，因为状态一定是会变大的，那么我们就会在枚举的下面几个阶段枚举到当前的状态然后转移，所以并不需要一次考虑太多位，只考虑下一位就可以了

P2396 yyy loves Maths VII

这个题我们就考虑状态就可以了（根本不配是一道紫题嘛）（但是这个题卡常）（毒瘤出题人）

在当前状态，我们只需要枚举出来最后一张卡片使用的那一张就可以了

不过这个题倒是提供了一个在做状压题的很好的优化方法：

使用lowbit运算进行优化时间（省的离散化

成功从1.5s优化到了996ms（刚刚好卡过去

P4363 [九省联考 2018] 一双木棋 chess

这个题……这谁timi想的出来啊

（不愧是tbl省选的时候没做出来的题）（啊虽说是他在高一的时候没做出来

首先我们发现：题目中给定的条件，如果说这个地方可以放棋子，这个棋子必须是左上角全都有棋子

那么这就可以构成一个台阶一样的形状

并且这个台阶还一定是左下角到右上角

那么（由于之前做组合数的题目的时候发现了网格图上的路径这件事情。。。

我们就可以状压轮廓线，一定是向上走n次，向右走m次

那么我们状压轮廓线转移的时候就相当于是把轮廓线的一个1左移把01变成10

（手模去

P5005 中国象棋 - 摆上马

（讨厌的题。。。

我们会发现象棋中有一个规则叫做绊马腿……如果两个格子紧挨着就不能走哪个方向的日字

那么我们状压的时候只需要考虑的就是前面的两行

数据范围6是可以过去的

那么我们考虑绊马腿的情况

如果说左右绊马腿的话，我们把当前行的状态右移，然后按位与一下下，就会发现我们得到了所有右边马腿，然后我们把马腿右移一位，就可以得到上一行被绊的所有地方，然后把这几个地方抛出去，再进行判断，左移是一样的

上下绊马腿的话，我们需要把相邻的两行按位与，然后可以求出来有马腿的位置，然后把有马腿的位置进行右移，判断，左移也是一样

并且我们会发现，这样只是单向判断，所以还需要把刚才判断的这几个反转一下再求一边

并且（最大的坑点）卡空间！！！！！

滚动数组

然后你会发现，你的滚动数组的空间必须是严格的（1<<6)。。。我试了试1都不能加！！！

P2150 [NOI2015] 寿司晚宴

真timi的是道好题，完全做不出来

我们先想一下30分的做法

你会发现如果说两个数互质，那么这两个数的所有的质因数集合应该是不重叠的，那么我们就可以状压一下质因数集合

100分的时候。。。

只是质因数多了一点而已

但是我们发现500的数据，最多会有一个大于22的质因数

那么我们前面还按照30分做就可以，把最大的那个质因数拿出来重新算一下就可以

我们把所有的数字按照大质因数进行排序，大质因数一样的几个数字放到一起

然后对所有大质因数一样的几个数字放在一起考虑就可以