P1248 加工生产调度

· · 个人记录

明确研究对象是方案，而这里的方案指的是一个排列

即p为n个物品的加工顺序，p为[1,n]的一个排列

考虑对于一个方案如何计算它的代价

记f(n)为前i项的加工时间

则

f(n)=\max(\sum_{i=1}^{n}A_{p_i},f(n-1))+B_n

考虑把它变得可爱一点

f(n)=\max_{1\le k\le n}\{\sum_{i=1}^k A_{p_i}+\sum_{i=k}^nB_{p_i}\}

那么就有答案ans

ans=\min_{p}\{\max_{1\le k\le n}\{\sum_{i=1}^k A_{p_i}+\sum_{i=k}^nB_{p_i}\}\}

考虑能不能把k踹出来

ans=\min_{1\le k\le n}\{\min_{以k为分界点取max的p}\{\sum_{i=1}^k A_{p_i}+\sum_{i=k}^nB_{p_i}\}\}