BZOJ1096 [ZJOI2007]仓库建设

题目传送门 这是一道比较裸的动态规划斜率优化 考虑f[i]表示前i个工厂,其中第i个一定建了仓库的最小费用。 s1[i]表示i号点到n号点的距离 s2[i]表示1~i号点的所有物资运到n号点的费用,s2[i]=s2[i-1]+s1[i]*p[i] s3[i]表示1~i号点的物资数量 $$f[j]=m …