Codeforces round 493 Convert to Ones
一道很迷惑的题目。
英文题面就不粘了，题目大意就是
给定一串0-1序列，定义两种操作：
- 操作一：选取一连续子串倒置。
- 操作二：选取一连续子串把进行01互换（取反）。
并给出操作一和操作二的代价，分别为x和y。
操作到最后要把串变成只含1的串，问最小的操作代价
第一反应是区间dp， 枚举每个01区间， 发现根本没法做。
后来发现和dp毛关系都没有。
这个问题，对于每个区间，我们可以想象成一种积木的结构。
举个栗子， 1001100010， 我们把它划分一下， 100 11000 10
我们把一块积木倒转， 就可以让两段 0 拼成一段。0 的段落数就减一
也就是说， 我们每进行一次操作一， 操作二的数目就减一。
我们可以枚举操作一的数量
for(long long i=0; i<k; i++) ans = 1ll*min(i*x+(k-i)*y, ans);
一层循环， 可以 a 过
但其实还有更好的方法
我们每进行一次操作一， 操作二的数目就减一。也就是说，操作一增加的数目和操作二减少的数目是相同的
而他们的代价都是一定的，我们枚举的相邻两个k， ans的差值就是操作一二代价的差值。
换句话说， ans的变化是具有单调性的。
那就好办了， 比较两个端点就可以了。 也就是比较 (k-1)*x + y 和 k*y
代码也是相当好写