P3694 邦邦的大合唱站队 题解

这道题中，我们并不关心出列的是谁，而是出列的人数。

由于偶像数量很多，乐队的数量则很少，考虑状压 dp。

可以发现不管怎么排，怎么出列，最后的总人数是一直不变的，同时，每个乐队的总人数也是不变的（很显然的重要性质）。

假设状态  表示当前已经站好的乐队的编号集合，设总人数为 ，若他们从第一个位置开始站起，则他们所占用的位置一定是 。

我们不妨考虑站在最后一个位置的乐队，设其人数为 ，同样地，可以确定其所在区间一定是 。那么原本就在这个区间里的偶像就可以不用出列了，其他人全部出列即可。

最后我们定义  为初始状态下前  个位置中是  号乐队的人的个数，此信息和上述的  一样，都可以初始化后得到。

我们令  为状态  时的最小出列人数，显然的，对于  有：

其中  表示异或。

Code:

心情日记：

悲惨，数学又不及格……我的数学到底什么时候才会好一点啊……

好像和喜欢的女生待在一起啊，可惜她是年级第一啊，我怎么配得上她呢？对吧……