题目描述
有 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))
|