第 377 场周赛（哈希表，floyd, 记忆化搜索）

func numberGame(nums []int) []int {
    slices.Sort(nums)
    n := len(nums)
    res := []int{}
    for i := 0; i < n - 1; i += 2 {
        res = append(res, nums[i + 1])
        res = append(res, nums[i])
    }
    return res
}

func maximizeSquareArea(m int, n int, hFences []int, vFences []int) int {
    h := f(hFences, m)
    v := f(vFences, n)

    res := 0

    for x := range h {
        if v[x] {
            res = max(res, x)
        }
    }

    if res == 0 {
        return -1
    }
    return res * res % 1_000_000_007
}

func f(a []int, mx int) (set map[int]bool) {
    a = append(a, 1, mx)
    slices.Sort(a)
    set = make(map[int]bool)
    for i, x := range a {
        for _, y := range a[i+1:] {
            set[y - x] = true
        }
    }
    return
}

func minimumCost(source string, target string, original []byte, changed []byte, cost []int) int64 {
    dis := [26][26]int{}
    for i := range dis {
        for j := range dis {
            if j != i {
                dis[i][j] = 1e13
            }
        }
    }

    for i, c := range cost {
        x := original[i] - 'a'
        y := changed[i] - 'a'
        dis[x][y] = min(dis[x][y], c)
    }

    for k := range dis {
        for i := range dis {
            for j := range dis {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
            }
        }
    }

    var ans int64 = 0
    for i, b := range source {
        ans += int64(dis[b - 'a'][target[i] - 'a'])
    }

    if ans >= 1e13 {
        return -1
    }

    return ans
}   

func minimumCost(source string, target string, original []string, changed []string, cost []int) int64 {
    const inf = math.MaxInt / 2
    type node struct {
        son[26] *node
        sid int // 编号
    }
    root := &node{}
    sid := 0
    put := func(s string) int {
        o := root
        for _, b := range s {
            b -= 'a'
            if o.son[b] == nil {
                o.son[b] = &node{sid: -1}
            }
            o = o.son[b]
        }
        if o.sid < 0 {
            o.sid = sid
            sid ++ 
        }

        return o.sid
    }

    m := len(cost)
    dis := make([][]int, m * 2)
    for i:= range dis {
        dis[i] = make([]int, m * 2)
        for j := range dis[i] {
            if j != i {
                dis[i][j] = inf
            }
        }
    }

    for i, c := range cost {
        x := put(original[i])
        y := put(changed[i])
        dis[x][y] = min(dis[x][y], c)
    }


    for k := 0; k < sid; k ++ {
        for i := 0; i < sid; i ++ {
            if dis[i][k] == inf {
                continue
            }
            for j := 0; j < sid; j ++ {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
            }
        }
    }

    n := len(source)
    memo := make([]int, n)
    for i := range memo {
        memo[i] = -1
    }

    var dfs func(int) int
    dfs = func(i int) int {
        if i >= n {
            return 0
        }
        ptr := &memo[i]
        if *ptr != -1 {
            return *ptr
        }

        res := inf
        if source[i] == target[i] {
            res = dfs(i + 1)
        }

        p, q := root, root
        for j := i; j < n; j ++ {
            p = p.son[source[j] - 'a']
            q = q.son[target[j] - 'a']
            if p == nil || q == nil {
                break
            }
            if p.sid >= 0 && q.sid >= 0 {
                res = min(res, dis[p.sid][q.sid] + dfs(j + 1))
            }
        }
        *ptr = res
        return res
    }

    ans := dfs(0)
    if ans == inf {
        return -1
    }
    return int64(ans)
}