[斜率优化DP]bzoj1096 - cool's Blog
[斜率优化DP]bzoj1096
1096: [ZJOI2007]仓库建设
Description
L公司有N个工厂，由高到底分布在一座山上。如图所示，工厂1在山顶，工厂N在山脚。 由于这座山处于高原内陆地区（干燥少雨），L公司一般把产品直接堆放在露天，以节省费用。突然有一天，L公司的总裁L先生接到气象部门的电话，被告知三天之后将有一场暴雨，于是L先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。由于地形的不同，在不同工厂建立仓库的费用可能是不同的。第i个工厂目前已有成品Pi件，在第i个工厂位置建立仓库的费用是Ci。对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，而由于L公司产品的对外销售处设置在山脚的工厂N，故产品只能往山下运（即只能运往编号更大的工厂的仓库），当然运送产品也是需要费用的，假设一件产品运送1个单位距离的费用是1。假设建立的仓库容量都都是足够大的，可以容下所有的产品。你将得到以下数据： 工厂i距离工厂1的距离Xi（其中X1=0）; 工厂i目前已有成品数量Pi; 在工厂i建立仓库的费用Ci; 请你帮助L公司寻找一个仓库建设的方案，使得总的费用（建造费用+运输费用）最小。
Input
第一行包含一个整数N，表示工厂的个数。接下来N行每行包含两个整数Xi, Pi, Ci, 意义如题中所述。
Output
仅包含一个整数，为可以找到最优方案的费用。
Sample Input
0 5 10
5 3 100
9 6 10
Sample Output
暑假的时候就听lbn（%%%）讲过斜率优化，不过那个时候连单调队列都不太动，根本不知道斜率优化是啥。
最近一直在做DP题，但dp水平还是十分的差。
这题最基本转移方程式是
f[i] = min(f[j]+Σ(p[i]-p[x])*a[x](j<=x<=i)(j<i)
这个复杂度显然是O(n2)的。
用单调队列的思想，设k<j<i
如果f[k]+Σ(p[i]-p[x])*a[x](k<=x<=i)>f[j]+Σ(p[i]-p[x])*a[x](j<=x<=i)，那么k是无用的。
我们展开式子(sumap[i] = Σ(a[x]*p[x])
f[j]+sumap[j]-f[k]-sumap[k]<p[i]*(sum[j]-sum[k])
因为sum[j]-sum[k]>0
(f[j]+sumap[j]-f[k]-sumap[k])/(sum[j]-sum[k])<p[i]
我们把这个式子想象成斜率，j对应了（sum[j],f[j]+sumap[j])这个点，
所以如果j与k的斜率小于p[i]，那么就可以舍掉k。
g[k,j]表示k到j的斜率。
若g[k,j]>g[j,i],则j是无用的。
为什么呢？如果p[i]<g[j,i]<g[k,j],则那么显然由上可知是无用的
如果g[j,i]<p[i]，而p[i]<p[i+1]（p是单调的，这也正是斜率优化的关键），g[j,i]<p[i+1]，那么j也是无用的。
所以就可以用单调队列维护。
下附代码
for (int i = 1;i <= n;i++)
{
for (;l<r&&(dy(q[l+1])-dy(q[l]))<=p[i]*(dx(q[l+1])-dx(q[l]));l++);
f[i] = f[q[l]]+(sum[i]-sum[q[l]])*p[i]-(sumap[i]-sumap[q[l]])+w[i];
for (;l<r&&(dy(i)-dy(q[r]))*(dx(q[r])-dx(q[r-1]))<=(dy(q[r])-dy(q[r-1]))*(dx(i)-dx(q[r]));r--);
q[++r] = i;
}
BZOJ1010也是到斜率优化。
2023年2月03日 01:09
The popular brand Tenda supplies various wireless routers which well known for easy configuration of the WiFi network. Once a new Router bought, one should make it ready to configure such that their LAN connection does move to WiFi to used by multiple devices. Tenda Login Tenda is the most preferred brand in customer premises wireless equipment due to its good range and stable connection. This difference in Bandwidth does allow the WiFi Router to handle better internet for any kind of bandwidth requested.