acwing300任务安排1对“费用提前计算”的解释

发布时间 2023-11-01 21:54:04作者: 最爱丁珰

我们考查对任意一种方案答案的构成

假设最终方案只有这三段

那么很显然,答案为$$(S+sumT_[i])\cdot sumC_{i}+(2S+sumT_[j])\cdot (sumC_{j}-sumC_{i})+(3S+sumT_[n])\cdot (sumC_{n}-sumC_{j})$$

我们换一种写法,答案为$$sumT_{i}\cdot sumC_{i}+sumT_{j}\cdot (sumC_{j}-sumC_{i})+sumT_{n}\cdot (sumC_{n}-sumC_{j})+S\cdot sumC_{n}+S\cdot (sumC_{n}-sumC_{i})+S\cdot (sumC_{n}-sumC_{j})$$

前面三项是自身的贡献,后面三项是启动时间对答案的贡献

所以我们将\(f[i]\)的意义更加具体化:表示已经安排好了前\(i\)个任务,这些任务自身的贡献加上启动时间对答案的总贡献的最小值,这就是费用提前计算