任务

题意

• 有两台机器n个任务,每个任务i在机器A完成时间是a[i],B上面完成时间是b[i],任务i可以被处理当前仅当每个任务j(i>j)已经被完成或者正在进行.求最少完成任务的时间(n<2000,a[i],b[i]<=3000)

分析

• 首先读清楚题目意思

**任务i可以被处理当前仅当每个任务j(i>j)已经被完成或者正在进行**

上面这句话有什么用?

仔细分析后可以发现上面这个性质确保了执行任意任务的时候机器AB时间差不会超过3000

假如A比B将少运行时间超过3000,那么现在放置任务i+1
-    那么任务i+1不能放置机器A最开始空闲的时候,因为这样B机器必然(B多A3000时间)有任务j(j<i)还没有没执行;那么任务i+1只能当道B机器运行最后一个任务j的起始时间上去,这样的方案必然没有比任务j放置到A机器方案优(可以画图模拟一下)
-    把任务i+1放置到机器B,那么这种方案将继续造成恶性循环又进入此状态,显然最终这种方案不优

所以任一个任务选择的时候AB机器运行结束时间差不能够3000

**建立状态**

dp[i][j]表示完成任务i并且机器AB运行结束时间差为j的最少时间,(j>0表示A比B多j,否则B比A多-j,后面右移3000,保证都是正数)

**状态转移**

dp[i][j]由dp[i-1][j+a[i]和dp[i-1][j-b[i]]转移过来,其中要注意任务i放到机器A或B中可能对时间没有影响

思考

• 错误分析

-    没有对非法状态进行限制,比如状态转移的时候,放置任务i到机器A,必须设定任务i时间当值 >= B机器最后一个任务j放置时间!!!确保i之前的任务被处理完或正被处理
-    没有考虑任务i放置到机器A后对时间无影响的情况