标签为 [斜率优化] 的文章

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]=min_{j=0}^{i-1}{f[j]+s2[i]-s2[j]-s1[i]*(s3[i]-s3[j])}$$ 考虑对于i的两个决策点j,k(j<k),所以(s3[k]-s3[j])>0假设k比j优,即 $$f[j]+s2[i]-s2[j]-s1[i](s3[i]-s3[j])>=f[k]+s2[i]-s2[k]-s1[i](s3[i]-s3[k])$$ $$f[j]-s2[j]-f[k]+s2[k]>=s1[i]*(s3[k]-s3 ......