用2台处理机a和b处理n个作业。设第i个作业交给机器a处理时需要时间ai.若由机器b来处理,则需要时间bi。由于各作业的特点和机器的性能关系,很可能对于某些i,有ai≥bi，而对于某些j≠i,有aj< bj;。既不能将一个作业分开由2台机器处理，也没有一台机器能同时处理2个作业。设计个动态规划算法,使得这2台机器处理完这n个作业的时间最短(从任何一台机器开工到最后一台机器停工的总 时间)。 研究一个实例:(a1,a2 ,a3,a4,a5,a5) = (2,5,7,10,5,2); (b1,b2,b3,b4,b5,b6)= (3,8,4,11,3,4)。

### 回答1：
这是一道经典的任务调度问题，可以使用动态规划算法来解决。

首先，定义一个二维数组dp[i][j]表示前i个作业分配给a和b两台机器处理，其中a已经处理了j个作业的最短时间。则状态转移方程为：

dp[i][j] = min(dp[i-1][j-1]+ai, dp[i-1][j]+bi)

其中，第i个作业可以分配给a或b两台机器处理，如果分配给a，则a已经处理了j-1个作业，需要加上ai的时间；如果分配给b，则a已经处理了j个作业，需要加上bi的时间。取两者中的最小值即可。

最终的答案为dp[n][n/2]，即前n个作业分配给a和b两台机器处理，a已经处理了n/2个作业的最短时间。

对于给定的实例，可以得到以下的状态转移表：

j 0 1 2 3 4 5
i
0 0 2 7 14 19 24
1 3 5 10 17 22 27
2 7 8 12 19 24 29
3 11 13 14 21 26 31
4 14 16 18 21 26 31
5 16 18 20 23 26 31

最终的答案为31，即两台机器处理完这6个作业的最短时间为31。

### 回答2：
这道题可以采用动态规划的思想，用一个二维数组dp[i][j]表示a机器处理前i个作业，b机器处理前j个作业所需的最短时间，i和j都从0开始。

对于dp[i][j]的状态转移，分为以下两种情况：

1. 第i个作业交给a机器处理，第j个作业交给b机器处理。则dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + bi。

2. 第i个作业交给b机器处理，第j个作业交给a机器处理。则dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + ai。

最终的答案即为dp[n][n]。根据题目要求，不能将一个作业分开由两台机器处理，因此任意时刻a机器和b机器只能处理一个作业。

用给定的实例来说明：

a = [2, 5, 7, 10, 5, 2]， b = [3, 8, 4, 11, 3, 4]

设dp数组为6 x 6 的矩阵，初始值为0。

| | 0 | 1 | 2 | 3 | 4 | 5 |
| --- |---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 3 | 0 | 0 | 0 | 0 | 0 |
| 2 | 8 | 13 | 20 | 23 | 23 | 23 |
| 3 | 12 | 23 | 33 | 46 | 49 | 53 |
| 4 | 23 | 38 | 49 | 70 | 75 | 78 |
| 5 | 28 | 46 | 63 | 78 | 83 | 88 |

在dp表格中，第i行第j列表示a机器处理前i个作业，b机器处理前j个作业所需的最短时间。根据状态转移方程，可以推导出每个元素的值。

例如dp[3][4]，表示a机器处理前3个作业，b机器处理前4个作业所需的最短时间。这个值可以由上一个状态dp[2][4]和dp[3][3]转移而来，使用状态转移方程即可计算得到。

最终答案为dp[5][5] = 88，表示两台机器处理完这六个作业的时间最短为88。

### 回答3：
这道题目可以使用动态规划算法来解决。我们设f[i][j]为前i个作业中，由机器A处理j个作业的最短时间。那么由机器B处理的作业个数为i-j个。

因此，状态转移方程为：

f[i][j] = min(f[i-1][j]+a[i], f[i-1][j-1]+b[i]) (j≥1)
f[i][0] = f[i-1][0]+a[i]

其中，第一条状态转移方程表示第i个作业由机器A处理，则前i-1个作业由机器A处理的数量是j，由机器B处理的数量是i-j，此时第i个作业由机器A处理，所需时间为a[i]；第二条状态转移方程表示第i个作业由机器B处理，则前i-1个作业由机器A处理的数量是j-1，由机器B处理的数量是i-j-1，此时第i个作业由机器B处理，所需时间为b[i]。

为了求出最短时间，我们需要枚举所有的j，然后取其中的最小值，即：

ans = min(f[n][j]+max(sum(a)-sum(b[j]), sum(b)-sum(a[j])))

其中，sum(a)和sum(b)分别表示所有作业在机器A和机器B上处理所需的总时间，sum(a[j])和sum(b[j])分别表示前j个作业在机器A和机器B上处理所需的总时间。

最终的答案即为ans。