Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


  1. 「ZJOI2007」仓库建设 - 斜率优化 DP

    i i 个工厂目前已有成品 Pi P_i 件,在第 i i 个位置建立仓库的费用是 Ci C_i 。对于没有建立仓库的工厂,其产品应被运往其他的仓库进行储藏,而由于公司产品的对外销售处设置在山脚的工厂 N N ,故产品只能往山下运(即只能运往编号更大的工厂的仓库),当然运送产品也是需要费用的,假设一件产品运送 1 1 个单位距离的费用是 1 1 。假设建立的仓库容量都都是足够大的,可以容下所有的产品。你将得到以下数据:

    1. 工厂 i i 距离工厂 1 1 的距离 xi x_i (其中 x1=0 x_1 = 0 );
    2. 工厂 i i 目前已有成品数量 pi p_i
    3. 在工厂 i i 建立仓库的费用 ci c_i

    请你帮助公司寻找一个仓库建设的方案,使得总的费用(建造费用 + 运输费用)最小。

    于  BZOJ, COGS, DP, ZJOI, 单调队列, 斜率优化 继续阅读