CF1733D2 Zero-One (Hard Version) 题解

· · 题解

提示 1

首先统计 a[i] \ne b[i] 的 i，记到数组 p 中，由于每次操作只能改变 2 个这样的 i，那么如果 p 的长度是奇数，则输出 -1。

提示 2

分类讨论：y \le x 和 y > x。

提示 3

设 m 为 p 的长度。对于 y \le x：

提示 4

对于 y > x，可以用动态规划求解。

提示 5

设 f[i] 表示修改 p 的前 i 个位置的最小花费，那么对于 p[i]，有两种方案：

  1. 找个不相邻的位置操作，花费 y，那么对于 p[i] 相当于花费 y/2，因此 f[i] = f[i-1] + y/2
  2. 不断找相邻的位置操作，把 p[i] 和 p[i-1] 一组，那么需要操作 p[i]-p[i-1] 次，因此 f[i] = f[i-2] + (p[i]-p[i-1])\cdot x

两者取最小值，即

f[i] = \min(f[i-1] + y/2, f[i-2] + (p[i]-p[i-1])\cdot x)

初始值 f[0]=0，f[1]=y，答案为 f[m]。

代码实现时，为了方便处理 y/2，可以把所有数都乘 2，最后再除以 2。

此外，计算 f 的过程可以用两个变量滚动计算。

答疑

问：为什么花费 y 的时候，不用考虑相邻的情况？

答：因为 y>x，如果相邻，从 f[i-2] 转移过来是更优的。

问：转移方程没有对选了多少个 y 加以限制，如果选了奇数个 y 怎么办？

答：注意 m 是偶数，那么一定会选偶数个 y，你可以从记忆化搜索的角度来思考这一点。

代码（Golang）

package main
import("bufio";."fmt";"os")

func main() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()

    var T, x, y int64
    var a, b []byte
    for Fscan(in, &T); T > 0; T-- {
        Fscan(in, &a, &x, &y, &a, &b)
        p := []int{}
        for i, c := range a {
            if c != b[i] {
                p = append(p, i)
            }
        }
        m := len(p)
        if m%2 > 0 {
            Fprintln(out, -1)
        } else if m == 0 || y <= x {
            if m == 2 && p[0]+1 == p[1] {
                Fprintln(out, min(y*2, x))
            } else {
                Fprintln(out, int64(m/2)*y)
            }
        } else {
            f, g := int64(0), y
            for i := 1; i < m; i++ {
                f, g = g, min(g+y, f+int64(p[i]-p[i-1])*x*2)
            }
            Fprintln(out, g/2)
        }
    }
}

func min(a, b int64) int64 { if a > b { return b }; return a }

复杂度分析