This page looks best with JavaScript enabled

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

 ·  ✏️ About  555 words  ·  ☕ 2 mins read · 👀7 views

L 公司有 N 个工厂,由高到底分布在一座山上。工厂 1 在山顶,工厂 N 在山脚。

由于地形的不同,在不同工厂建立仓库的费用可能是不同的。第 i 个工厂目前已有成品 Pi 件,在第 i 个工厂位置建立仓库的费用是 Ci

对于没有建立仓库的工厂,其产品应被运往其他的仓库进行储藏,而由于 L 公司产品的对外销售处设置在山脚的工厂 N ,故产品只能往山下运(即只能运往编号更大的工厂的仓库),当然运送产品也是需要费用的,假设一件产品运送 1 个单位距离的费用是 1

假设建立的仓库容量都都是足够大的,可以容下所有的产品。你将得到以下数据:

  • 工厂 i 距离工厂 1 的距离 Xi(其中 X1=0 );
  • 工厂 i 目前已有成品数量 Pi ;
  • 在工厂 i 建立仓库的费用 Ci ;

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

链接🔗

Luogu P2120

题解🔗

暴力搞搞式子:

dp[i]=minj=0i1(dp[j]+ci+w=j+1i(xixw)×pw) dp[i]=minj=0i1(dp[j]+ci+w=j+1i(xi×pwxw×pw)) dp[i]=minj=0i1(dp[j]+xiw=j+1ipww=j+1ixw×pw))+ci

ai=w=1ipwbi=w=1ixw×pw,原式化为

dp[i]=minj=0i1(dp[j]+xi×(aiaj)(bibj))+ci

如果令 j<k<i ,则 kj 优等价于:

dp[j]+xi×(aiaj)(bibj)dp[k]+xi×(aiak)(bibk) dp[j]xi×aj+bjdp[k]xi×ak+bk (dp[j]+bj)(dp[k]+bk)xi(ajak)

因为 aj<ak ,即 ajak<0 ,所以有

(dp[j]+bj)(dp[k]+bk)ajakxi

注意到 xi 单调递增,即如果在某个时刻 kj 优,则以后其会一直更优,单调队列维护即可。

代码🔗


cqqqwq
WRITTEN BY
cqqqwq
A student in Software Engineering.


Comments