星空 题意转化,差分,状压DP

好题(爆搜和puts("2")一个分(雾)),不得不说思维真的强。

首先发现区间翻转很难受,考虑用差分(异或满足可逆性),注意是从0到n+1

然后就转化题意,操作改为选取距离为L的两个数异或1,我们需要把所有的1变成0(因为1代表前后两个数不同,0代表相同)

分情况考虑

不可能同时让两个0异或成1,所以:

1.一个0,一个1可以视为将1移动到0的位置

2.两个1可以认为将它俩全部消除

考虑一下可以bfs预处理出两个1消除的代价,时间复杂度O(nmk)。

进一步转化题意:

给定n个物品,每两个物品的消除都有一定代价,最小花费?

这就是普通的状压了,但要注意区分O(k*2^2k)和(k^2*2^2k)的打法

具体k*2^k的打法:

对于当前状态state,随便固定一个点,再枚举它和哪些物品同时消除,取min即可

这样做的话,相当于转移的时候只会转移固定一个点的状态,但实际上如果k^2枚举的话会有很多冗余状态,

一个state可以由k个last更新,就冗余啦。

原文地址:https://www.cnblogs.com/hzoi-kx/p/11337592.html