题解：AT_arc194_c [ARC194C] Cost to Flip

· · 题解

AT_arc194_c [ARC194C] Cost to Flip

题意

给出两个长度为 n 的 01 数组，其中 A 串为当前数组，B 为目标数组。给出代价数组 C。

你每次可以进行以下操作（也可以不进行），使最终得到 A 与 B 相等：

  1. 选择一个数 i，对 A_i 进行异或操作。

  2. 总代价加上 {\textstyle \sum_{i=1}^{n}} [A_i=1] C_i 。

求最小代价。

做法

通过观察，发现对于某一个 A_i，存在四种情况。

  1. 若 A_i=0,B_i=0 则一定不需要对其进行操作（证明显然）。

  2. 若 A_i=1,B_i=0 则一定要尽快把其置为 0，因为徒增代价显然是不利的。

  3. 若 A_i=0,B_i=1 则一定要把把 A_i 置为 1 的操作放在后面，因为过早增加代价显然也是不利的。

  4. 若 A_i=1,B_i=1，则发现可能会出现两种情况，一种是不改变他，使其一直进行贡献，一种是把它拆成 10+01。

显然对这个序列可以进行排序，对结果无影响。

我们显然发现会更改的 11 一定为 11 中代价较大的部分。

发现 10 和 01 的顺序已经固定，考虑把加入 11 的操作看作向这个序列插入。

显然具有单调性。可以枚举插入的位置。