斜率优化
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]+\sum\limits_{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: