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

题目描述

有 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))