2012-0053

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

假设当前时间为T，对于两个工作Si，Ti和Sj，Tj，试比较先i后j的价值A，和先j后i的价值B

{{{
A = T*Si + (T-Ti)*Sj = T*Si + T*Sj - Ti * Sj
B = T*Sj + (T-Tj)*Si = T*Si + T*Sj - Tj * Si

A - B = Tj * Si - Ti * Sj 
}}}

用A-B排序即得先完成那些任务会有更优的价值, 但是由于T的限制, 直接贪心取会导致后面可能出现有任务无法取到,所以只需要再做一个简单的背包DP即可。


By FJYsmall

假设当前时间为T，对于两个工作Si，Ti和Sj，Tj，试比较先i后j的价值A，和先j后i的价值B

A = T*Si + (T-Ti)*Sj = T*Si + T*Sj - Ti * Sj
B = T*Sj + (T-Tj)*Si = T*Si + T*Sj - Tj * Si
A - B = Tj * Si - Ti * Sj 

用A-B排序即得先完成那些任务会有更优的价值, 但是由于T的限制, 直接贪心取会导致后面可能出现有任务无法取到,所以只需要再做一个简单的背包DP即可。

By FJYsmall