2019校招真题--贝壳找房网--「伐木」

Posted on In Views: Disqus:

题目描述

有 n 颗树木，两个工具：锯子和斧头，对于每棵树木都给出了使用某种工具砍伐所用的时间，以及若想要换工具需要额外花费的时间，求砍完这些树木话费的最少时间。

示例：

输入：
3
20 40 20
10 4 25
90 100 5
输出：
139

解释：共有三颗木头，以下每行有三个数字，分别表示用锯子需要的时间、用斧头需要的时间、换工具需要的时间。

解题思路

  1. 深度优先搜索（DFS）。超时。
  2. 动态规划。用双状态 DP 表示到该树木为止，最后一次使用两种工具所需要的最小时间。而这两个状态都取决于前一棵树木的状态。

代码

Python 3.6

解法一：DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import sys


class Solution(object):
    def __init__(self):
        self.min_time = float("inf")

    def compute_time(self, nums):
        self.__dfs(0, len(nums), nums, 1, 0)
        return self.min_time


    def __dfs(self, left, right, nums, method, time):
        if left == right:
            self.min_time = min(time, self.min_time)
            return
        for cur_method in range(2):
            cur_time = nums[left][cur_method] if cur_method == method else nums[left][-1] + nums[left][cur_method]
            time += cur_time
            if time >= self.min_time:
                time -= cur_time
                continue
            self.__dfs(left + 1, right, nums, cur_method, time)
            time -= cur_time

if __name__ == "__main__":
    n = int(sys.stdin.readline().strip())
    nums = []
    for _ in range(n):
        nums.append(list(map(int, sys.stdin.readline().strip().split())))
    print(Solution().compute_time(nums))

解法二：DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import sys


def compute_time(n, nums):
    dp = [[0] * 2 for i in range(n)]
    # 0 表示锯子，1 表示斧头
    # 最开始拿着斧头
    dp[0][0] = nums[0][0] + nums[0][-1]
    dp[0][1] = nums[0][1]

    for i in range(1, n):
        # 上一次用的相同的直接加上本次的时间，上一次用的不同的加上本次的时间与换工具的时间，取较小者
        # 即为到该树木为止，以该工具结束的最小时间
        dp[i][0] = min(dp[i - 1][0] + nums[i][0], dp[i - 1][1] + nums[i][0] + nums[i][-1])
        dp[i][1] = min(dp[i - 1][1] + nums[i][1], dp[i - 1][0] + nums[i][1] + nums[i][-1])
    return min(dp[-1])


if __name__ == "__main__":
    n = int(sys.stdin.readline().strip())
    nums = []
    for _ in range(n):
        nums.append(list(map(int, sys.stdin.readline().strip().split())))
    print(compute_time(n, nums))
Related Posts