斜率优化

斜率优化

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:

斜率优化

斜率优化

上一篇:过渡属性transition


下一篇:mysqltest语法整理