cf老是错误代码cfci79

把最终需要亮的看做1不需要的看做0

要把全0序列,变成有至多10个1的01序列

不妨考虑把01序列变回全0序列(这样容易思考)

差分变成两个单点取反!

特殊加入n+1位置这样便于取反

首先,两个0取反一定不优可以用01取反和11取反来得到相同的效果

01取反,等价于1走到0,11取反等价于两个1消掉。

不断两个位置进行取反一萣是为了最后把两个1消掉!

也就是,其实是两个1的匹配

最短路建图f[i][j]表示i和j匹配的最小代价,也即最短路

一个问题是:不会影响其他位置的值吗

发现这个最短路的边,除了起点终点都恰好xor两次(虽然这样并不优)!不会影响其他的位置的值!

枚举和S的lowbit进行匹配的点

参考资料

 

随机推荐