斜率优化

斜率优化

hdu3507
要输出N个数字a[N]，输出的时候可以连续的输出，每连续输出一串，它的费用是 ：这串数字和的平方加上一个常数M。求最小的；
0 ≤ n ≤ 500000, 0 ≤ M ≤ 1000

首先最暴力的：dp[i]表示输出到i的最小费用是多少；(dp[i]=min{dp[j]+（s[i]-s[j])^2+M})其中s[i]表示1~i的前缀和；即sum

然后我们引入并且考虑斜率优化：

设k<j,并且j优于k；

(dp[j]+(s[i]-s[j])^2+M<dp[k]+(s[i]-s[k])^2+M)

(dp[j]+s[j]^2-2s[i]s[j]<dp[k]+s[k]^2-2s[i]s[k])//约掉都有的

((dp[j]+s[j]^2)-(dp[k]+s[k]^2)<2s[i]*(s[j]-s[k]))

(frac{(dp[j]+s[j]^2)-(dp[k]+s[k]^2)}{(s[j]-s[k])}<2s[i]) ·········①

把((s[j],dp[j]+s[j]^2))看做点；（从这里设(s[j]=x[j],dp[j]+s[j]^2=y[j]))

那么①左边就是点j和点k的斜率吖；

那么这道题，对于状态i，我们就可以找平面上（1~i-1）的一坨点，判断两者连线的斜率<2s[i],如果斜率<2s[i],说明被减数更优，否则减数更优；

然后显然两两枚举也不够优，我们考虑三个点jkl，

由图片可以看出kj的斜率>lk的斜率：

(frac{y[k]-y[j]}{x[k]-x[j]}>frac{y[l]-y[k]}{x[l]-x[k]})

关于kj的斜率，lk的斜率与2s[i]比较有三种可能：

① (2s[i]>frac{y[k]-y[j]}{x[k]-x[j]}>frac{y[l]-y[k]}{x[l]-x[k]})

此时k比j优，l比k优，因此l最优；

② (frac{y[k]-y[j]}{x[k]-x[j]}>2s[i]>frac{y[l]-y[k]}{x[l]-x[k]})

此时j比k优，l比k优，无法确定谁最优；

③ (frac{y[k]-y[j]}{x[k]-x[j]}>frac{y[l]-y[k]}{x[l]-x[k]}>2s[i])

此时j比k优，k比l优，因此j最优；

但不管怎样，我们可以发现，k不会是最优的！

k没用！（雾

然后我们可以推知：

当前所有点中，只有在最下方的点才会对最优值产生影响：

那么对于i点的最优值就是某一点的斜率最接近2s[i]并且小于2s[i]的点（二分来做nlogn）；

继续想新加入一个点c，

那么可以看到，ab点的斜率要比ac点的大，那么我们就可以将a点删去，同理b也可以删去，但是d要保留；

同时，因为斜率是递增的，所以如果某个点在这个状态所对应的点之前，它一定不可能再产生贡献，也可以直接删除掉；

这样每次删除队首保证答案就是队首元素，然后加入的点向队尾添加同时判断弹出一部分队尾元素，这样每个点只进队一次，复杂度就是O（n）的。

int getup(int j,int k){
	return dp[j]+sum[j]*sum[j]-dp[k]-sum[k]*sum[k];
}

int getdown(int j,int k){
	return 2*(sum[j]-sum[k]); 
}

int getdp(int i,int j){
	return dp[j]+(sum[i]-sum[j])*(sum[i]-sum[j])+m;	
}

head=tail=1;
q[1]=0;
for(int i=1;i<=n;i++){
	while(head<tail&&getup(q[head+1],q[head])//将队首不到正确答案的点弹出 
	<=sum[i]*getdown(q[head+1],q[head])) head++;//用乘法代替除法来保证精度
	//意思是保证①式要<=s[i] （这里的2也放到左边去了 
	
	dp[i]=getdp(i,q[head]);//将所有不和条件的都弹出了以后，队首就是答案 
	
	while(getup(i,q[tail])*getdown(q[tail],q[tail-1])//把除法转化成乘法； 
	<=getup(q[tail],q[tail-1])*getdown(i,q[tail]))
	tail--; 
	/*转化之前： getup(i,q[tail])/getdown(i,q[tail])计算新加入的结点和队尾结点的斜率 
	<=getup(q[tail],q[tail-1])/getdown(q[tail],q[tail-1]) 计算队尾结点的前一结点和队尾结点的斜率
	判断是否合法，如果不合法，我们将其删去； 
	*/ 
	q[++tail]=i;//把新节点加进去 
}

一模一样的练习题： bzoj3156

首先来看转移方程

定义f[i]表示在i建塔并计算完了i之前的最小花费。

未化简的方程：(f[i]=min{f[j]+a[i]+sumlimits_{k=j+1}^{i-1}(i-k)})

解释一下就是枚举一个j表示i上一个塔建在了哪里，这样j之前的值可以直接加上，然后+建第i个塔所需花费a[i]，对于i和j之间的所有点，都需要放木偶，每个木偶的花费就是i-k（花费是这个点右边建的第一个守卫塔i到这个点的距离）也就是(sum)；

然后化简：(f[i]=min{f[j]+a[i]+(i-j-1)*(i-j)/2})

考虑：i和j之间一共有i-j-1个点，我们可以找到每两个点，他们的价值之和是i-j，所以答案就是点数*距离/2；

设k>j，且k优于j。
f[k]+(i-k)*(i-k-1)/2+a[i]<f[j]+(i-j)*(i-j-1)/2+a[i]
设K=k+1,J=j+1 为了好推

最后一步手写一下，把K，J带回去：

(frac{2*(f[k]-f[j])+k*(k+1)-j*(j+1)}{k+k+1-j-j-1}=frac{2*(f[k]-f[j])+k*k+k-j*j-j}{2*(k-j)})

然后是代码.jpg：