漆狗屋

Description

Dilpreet wants to paint his dog- Buzo's home that has n boards with different lengths[A1, A2,..., An]. He hired k painters for this work and each painter takes 1 unit time to paint 1 unit of the board.The problem is to find the minimum time to get this job done under the constraints that any painter will only paint continuous sections of boards, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.

（分配连续任务给n给人，求最晚完成分配任务的人所花的时间）

思路

动态规划（递归）

在每一步递归中，取下面结果的最小值：

1. max（arr[0]，剩下的人和任务分配方式的最小值）

2. max（arr[0] + arr[1]，剩下的人和任务分配方式的最小值)

3. max（arr[0] + arr[1] + arr[2]，剩下的人和任务分配方式的最小值)

用伪码表示就是：

set ans = max_int

for i in [0, 1, 2...n-1]

​ taskval = sum tasks val from index 0 to i

​ remain_min_ans = recursive(i+1, remain_people)

​ ans = min(ans, max(taskval, remain_min_ans) )

参考实现（O(n^2, n是任务数量)

from functools import lru_cache

def solve(p, tasks):
    @lru_cache(None)
    def dfs(rp, it):
        if rp == 1:
            return sum(tasks[it:])
        if it == len(tasks) - 1:
            return tasks[-1]
        rp -= 1

        ans, cursum = float('inf'), 0
        for j in range(it, len(tasks)):
            cursum += tasks[j]
            ans = min(ans, max(cursum, dfs(rp, j+1)))
        return ans

    return dfs(p, 0)

完整代码

O_NJU_JK