周赛350 | 顾澜的技术小站

2739. 总行驶距离

解题思路：

根据题意，每消耗5升，就会补充1升，那就相当于每次只消耗4升，可以补充的燃油就等于 $mainTank/4$

假设 $mainTank$ 正好是4的倍数，最后一次是得不到补充的，所以实际上补充的燃油应该是 $(mainTank-1)/4$

这里额外补充的燃油不可以超过副油箱的总量

示例代码：

func distanceTraveled(mainTank int, additionalTank int) int {
    return (min((mainTank-1)/4, additionalTank) + mainTank) * 10
}
func min(a, b int) int {if a < b {return a}; return b}

2740. 找出分区值

解题思路：

将数组排序，最小值必然是两个相邻元素的差，假设其分别为 $nums[i-1]$ 和 $nums[i]$ ，以这两个数为界限，即可满足题意。

示例代码：

func findValueOfPartition(nums []int) int {
    sort.Ints(nums)
    res := math.MaxInt
    for i := 1; i < len(nums); i++ {
        res = min(res, nums[i]-nums[i-1])
    }
    return res
}

func min(a, b int) int { if a < b { return a }; return b }

2741. 特别的排列

解题思路(回溯)：

使用回溯的思路，定义 $dfs(track, j)$ ，其中 $track$ 为数组，存储已选择下标， $j$ 表示上一次选择的下标。同时使用全局 $used$ 标记是否选择过。

当数组 $tarck$ 长度等于 $nums$ 的长度时，表示找到一个特别的排列，直接返回。

枚举当前要选择的下标 $k$ ，如果 $nums[k]$ 与 $nums[j]$ 满足整除的要求，将 $k$ 加入 $track$ 数组中并标记 $used$ 为已使用，并进行回溯，结束回溯从 $track$ 中取出 $k$ 并重置 $used$ 中 $k$ 的状态

枚举 $nums$ 中的每一个元素，求和

示例代码：

func specialPerm(nums []int) int {
    const mod int = 10e9 + 7
    used := make(map[int]bool)
    var dfs func(track []int, j int) int

    dfs = func(track []int, j int) (res int) {
        if len(track) == len(nums) {
            return 1
        }

        for k, x := range nums {
            if !used[k] && (nums[j]%x != 0 || x%nums[j] != 0) {
                track = append(track, x)
                used[k] = true
                res = (res + dfs(track, k)) % mod
                used[k] = false
                track = track[:len(track)-1]
            }
        }
        return res
    }
    var res int
    for i, num := range nums {
        used[i] = true
        res = (res + dfs([]int{num}, i)) % mod
        used[i] = false
    }
    return res
}

这样写下来代码阅读性很高，但是有个致命缺点，因为 $track$ 中的值是无序的，做剪枝很麻烦(使用下面的集合可以进行剪枝)，时间复杂度为 $n!$ 会超时

解题思路(回溯+位运算)：

前置知识：从集合论到位运算，常见位运算技巧分类总结！

一眼动态规划，定义 $dfs(i, j)$ 表示当前集合为 $i$ ，上一次选择的数下标是 $j$ 时，可以构造除特别排列的个数

枚举当前要选择的下标 $k$ ，如果 $nums[k]$ 与 $nums[j]$ 满足整除的要求，则

$dfs(i,j) = \sum_{k \in i} dfs(i\backslash \left\{ k \right\}, k)$

其中 $i\backslash \left\{ k \right\}$ 表示从集合 $i$ 中移除 $k$

当 $i$ 为0时，集合已经使用完，表示找到一个特别的排列

设全集 $U=\left\{0,1,2,...,n-1\right\}$ ，枚举每一个下标 $j$ ，求特别列第一个数下标为 $j$ 的特别列个数 $dfs(U\backslash \left\{ j \right\}, j)$ ，并求和即为答案

示例代码：

func specialPerm(nums []int) int {
    const mod int = 1e9 + 7
    n := len(nums)
    m := 1 << n - 1
    memo := make([][]int, m)
    for i := range memo {
        memo[i] = make([]int, n)
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }

    var dfs func(int, int) int
    dfs = func(i int, j int) (res int) {
        if i == 0 {
            return 1
        }

        if memo[i][j] != -1 {
            return memo[i][j]
        }

        for k, x := range nums {
            if i>>k&1 == 1 && (nums[j]%x == 0 || x%nums[j] == 0) {
                res = (res + dfs(i^(1<<k), k)) % mod
            }
        }
        memo[i][j] = res
        return res
    }
    var res int
    for i := range nums {
        res = (res + dfs(m^(1<<i), i)) % mod
    }
    return res
}

解题思路(递推)：

将递归改为递推(循环)，变为自定向上计算，具体做法：

将 $dfs$ 改为 $dp$ 数组
递归改为循环（每个参数对应一层循环）
递归边界改为 $dp$ 数组的初始值

数组 $d[i][j]$ 的含义与状态转义方程 $dfs(i,j)$ 是一样的

$dp[i][j] = \sum_{k \in i} dfs(i\backslash \left\{ k \right\}, k)v$

初始值 $dp[0][j] = 1$ 。( $dfs(0,j) = 1$ )

答案为 $dp[U\backslash \left\{ j \right\}][j]$ 之和。 ( $dfs(U\backslash \left\{ j \right\}, j)$ )

示例代码：

func specialPerm(nums []int) int {
    const mod int = 1e9 + 7
    n := len(nums)
    m := 1<<n - 1
    dp := make([][]int, m)
    dp[0] = make([]int, n)
    for i := range dp[0] {
        dp[0][i] = 1
    }

    for i := 1; i < m; i++ {
        dp[i] = make([]int, n)
        for j, x := range nums {
            for k, y := range nums {
                if i>>k&1 == 1 && (y%x == 0 || x%y == 0) {
                    dp[i][j] = (dp[i][j] + dp[i^(1<<k)][k]) % mod
                }
            }
        }
    }

    var res int
    for i := range nums {
        res = (res + dp[m^(1<<i)][i]) % mod
    }
    return res
}

2742. 给墙壁刷油漆

解题思路(DFS)：

对于每一堵墙，我们都可以选择付费或者免费。

如果付费刷第 $i$ 堵墙，开销加上 $cost[i]$ ，且付费时间和加上 $time[i]$
如果免费刷第 $i$ 堵墙，免费时间和加一，开销不变

因此定义 $dfs(i,j,k)$ 表示刷完 $0\sim i$ 面墙，当前累计付费时间为 $j$ ，免费时间为 $k$ ，最少开销为多少。这里付费时间 $j$ 和免费时间 $k$ 为互斥关系，因为两个油漆匠同时工作，重新定义 $j$ 为「付费时间和」减去「免费时间和」。

付费刷第 $i$ 面墙： $dfs(i,j) = dfs(i-1, j+time[i])+cost[i]$
免费刷第 $i$ 面墙： $dfs(i,j) = dfs(i-1,j-1)$

去两种情况最小值：

$dfs(i,j) = min(dfs(i-1, j+time[i])+cost[i], dfs(i-1,j-1))$

如果 $j\geq n-i$ ，说明剩余的墙都可以免费刷，即 $dfs(i,j) = 0$

我们是从后往前刷，所以递归入口为 $dfs(0, 0)$

示例代码：

func paintWalls(cost, time []int) int {
    n := len(cost)
    memo := make([][]int, n)
    for i := range memo {
        memo[i] = make([]int, 2*n+1) // time[i] <= 500
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }

    var dfs func(int, int) int // 刷前 i 堵墙,且付费时间和为 j 最少开销
    dfs = func(i, j int) int {
        if j-n >= n-i { // 入口处j+n产生了偏移量
            return 0 // 剩余的墙都可以免费刷
        }

        if i == n {
            return math.MaxInt / 2
        }

        if memo[i][j] == -1 {
            memo[i][j] = min(dfs(i+1, j+time[i])+cost[i], dfs(i+1, j-1))
        }
        return memo[i][j]
    }
    return dfs(0, n) // 加上偏移量 n，防止负数
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

解题思路（0-1背包）:

上述解题思路很像 0-1 背包，其实他就是：

根据题意，「 $付费刷墙个数 + 免费刷墙个数 = n$ 」，同时「 $付费刷墙时间之和 \geq 免费刷墙时间之和(免费刷墙个数)$ 」，结合着两个式子可得「 $付费刷墙时间之和 \geq n - 付费刷墙个数$ 」，移项可得：「 $sum(付费刷墙时间+1) \geq n$ （把个数拆解为1+1+1+…）。

把 $time[i]+1$ 看成物品体积， $cost[i]$ 看成物品价值，问题变成：从 $n$ 个物品中选择体积和至少为 $n$ 的物品，价值和最小是多少？

这是 0-1 背包的一种「至少装满的变形」，定义 $dfs(i,j)$ 表示考虑前 $i$ 个物品，剩余还需凑出 $j$ 的体积，此时最小价值和

依旧用「选或不选」来思考，可以得到类似的状态转移方程：

$dfs(i,j) = min(dfs(i-1,j-time[i]-1), dfs)(i-1,j)$

递归边界：如果 $j \leq 0$ ，那么不需要再选任何物品了，返回 0；如果 $i \lt 0$ ，返回无穷大

递归入口： $dfs(n-1,n)$ ，表示体积和至少为 $n$

示例代码：

func paintWalls(cost, time []int) int {
    n := len(cost)
    memo := make([][]int, n)
    for i := range memo {
        memo[i] = make([]int, n+1)
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }
    var dfs func(int, int) int
    dfs = func(i int, j int) int {
        if j <= 0 { // 完成所需选择物品,后面什么也不用选了
            return 0
        }
        if i < 0 { // 已经没有物品可选,完成j所需,不合法
            return math.MaxInt / 2
        }

        if memo[i][j] == -1 {
            memo[i][j] = min(dfs(i-1, j-time[i]-1)+cost[i], dfs(i-1, j))
        }
        return memo[i][j]
    }

    return dfs(n-1, n)
}

转换为递推

func paintWalls(cost, time []int) int {
    n := len(cost)
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        dp[i] = math.MaxInt / 2
    }
    for i, c := range cost {
        t := time[i] + 1
        for j := n; j > 0; j-- {
            dp[j] = min(dp[max(j-t, 0)]+c, dp[j]) // j-t会小于0
            // memo[i][j] = min(dfs(i-1, j-time[i]-1)+cost[i], dfs(i-1, j))
        }
    }
    return dp[n]
}