Bakser's Blog

我是逗比。

bzoj3003[codeforces79D]LED[状压dp]

| Comments

因为是区间操作,考虑差分思想。

对于每一个位置,如果它与前一个位置颜色相同,就置为0,否则置为1.
显然区间反色操作就变成了1的移动,而且注意到两个1碰到一起就会消掉。
考虑状压dp,显然直接对n状压不可取而且从初状态出发不可做。
考虑终止状态,只有k个位置为1,差分后至多有2k个1,而任一次操作如果不是对1进行的显然都是浪费。
所以状压这2k个1,预先bfs计算两个1消掉需要几步(据说这里转化成了无向图最小权完美匹配问题),然后直接dp就可以了。
dp时有一些技巧,因为每次都要消去1,所以状态转移的方向是一定从大到小的,直接从大到小枚举状态即可。同时因为从大到小转移,每次不必枚举两对1,将其中一个1固定为lowbit,只枚举另一个就可以了。
过得人好像不是很多就不贴代码了。
把i打成1调三天不能逗更多。
提交记录被我刷的场面太美不敢看

Comments

comments powered by Disqus