题目描述
有 n 颗树木,两个工具:锯子和斧头,对于每棵树木都给出了使用某种工具砍伐所用的时间,以及若想要换工具需要额外花费的时间,求砍完这些树木话费的最少时间。
示例:
输入:
3
20 40 20
10 4 25
90 100 5
输出:
139
解释:共有三颗木头,以下每行有三个数字,分别表示用锯子需要的时间、用斧头需要的时间、换工具需要的时间。
解题思路
深度优先搜索(DFS)。超时。
- 动态规划。用双状态 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)] 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))
|