把最终需要亮的看做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进行匹配的点