** 斜率优化**
任务安排1 P2365 O(n^2)
时间为 t 费用为 c
状态表示:
f[i] 表示 将前i个任务分为若干批执行的费用+之后的启动时间 的最小值
重要思想:
1. 费用提前计算: 处理 s 对后面的任务的影响(启动的影响)
状态计算:
枚举最后一批 i i n
f[i] = min{f[q[hh]] + (∑ t[k])(∑ c[k]) + s*(∑ c[k]) | j∈[0 i-1]}
k=1 k=q[hh]+1 k=q[hh]+1
完成这个任务 这个任务及之后的任务的启动时间
技巧: 分为变化的部分和不变化的部分
边界: f[0] = 0