斜率优化dp_零衣贰的博客-爱代码爱编程

例题:排版问题

• 根据题目,我们不难得出朴素的转移方程:

  f i = m i n (   f j + ( ( w j + 1 + . . . w i ) − a ) 2   ) f_i=min(\space f_j+((w_{j+1}+...w_i)-a)^2\space) fi​=min( fj​+((wj+1​+...wi​)−a)2 )

• 用前缀和表示为:

  f i = m i n (   f j + ( s u m i − s u m j − a ) 2   ) f_i=min(\space f_j+(sum_i-sum_j-a)^2\space) fi​=min( fj​+(sumi​−sumj​−a)2 )

由于我们肯定要枚举 $i$ ,在枚举 $i$ 时, s u m i sum_i sumi​ 是个定值, 而 $a$ 是个常数,因此 s u m i − a sum_i-a sumi​−a 是个定值

• 我们令 c i = s u m i − a c_i=sum_i-a ci​=sumi​−a :

  f i = m i n (   f j + ( c i − s u m j ) 2   ) f_i=min(\space f_j+(c_i-sum_j)^2\space) fi​=min( fj​+(ci​−sumj​)2 )

• 展开:

  f i = m i n (   f j + c i 2 − 2 ∗ c i ∗ s u m j + s u m j 2   ) f_i=min(\space f_j+c_i^2-2*c_i*sum_j+sum_j^2\space) fi​=min( fj​+ci2​−2∗ci​∗sumj​+sumj2​ )

• 暂且将 min 去掉并移项

  f j + s u m j 2 = 2 ∗ c i ∗ s u m j + f i + c i 2 f_j + sum_j^2=2*c_i*sum_j+f_i+c_i^2 fj​+sumj2​=2∗ci​∗sumj​+fi​+ci2​

• 令 s u m j sum_j sumj​ 为 $x$, 令   f j + s u m j 2 \space f_j + sum_j^2  fj​+sumj2​ 为 $y$ , 令   2 ∗ c i \space 2*c_i  2∗ci​ 为 $k$

  y = k x + f i + c i 2 y=kx+f_i+c_i^2 y=kx+fi​+ci2​

形如一个一次函数

我们需要使得 f i f_i fi​ 最小,那么 f i + c i 2 f_i+c_i^2 fi​+ci2​ 即截距最小 （枚举 $i$ 时， c i c_i ci​ 相当于定值，上文提及）

对于每个不同的 $j$ ,其 $x,y$ 不同, 我们记为 x j , y j x_j,y_j xj​,yj​

对于每个不同的 $i$ ,其 $k$ 不同, 我们记为 k i k_i ki​

问题相当于给定一个一次函数的斜率 k i k_i ki​, 给定一些点 ( x j , y j ) (x_j,y_j) (xj​,yj​) ($0\le j<i$) ,一次函数需要过其中一点，求这些点中使得这个一次函数截距最小的点 ( x j , y j ) (x_j,y_j) (xj​,yj​) , 求出 $j$,然后再转移求得 f i f_i fi​

• 如图

• 现将直线向上平移，第一个碰到的点即为使得截距最小的点

• 可得最终最优的答案一定在一个凸壳（斜率逐渐增大）上
  

• 如何求出对于斜率为 k i k_i ki​ 直线第一个碰到的点？

  我们记 k i , j k_{i,j} ki,j​ 表示 $i,j$ 两点之间的斜率

  • 若 k i < k 1 , 2 k_i<k_{1,2} ki​<k1,2​ ，那么 $1$ 号点为第一个碰到的点

  • 

  • 若 k i = k 1 , 2 k_i=k_{1,2} ki​=k1,2​ ，那么 $1,2$ 号点都为第一个碰到的点，任选其一转移即可
    

  • 若 k 1 , 2 < k < k 2 , 3 k_{1,2}<k<k_{2,3} k1,2​<k<k2,3​ ，那么 $2$ 号点即为第一个碰到的点
    

  • $...$

  • 可得，对于任意 k i k_i ki​ ，使得 k j − 1 , j < k i < k j , j + 1 k_{j-1,j}< k_i< k_{j,j+1} kj−1,j​<ki​<kj,j+1​ 的 $j$ 即为第一个碰到的点（这里小于号取不取等号都可以，如上文第二种情况所述）

• 求出第一个碰到的点后，我们即可求出 f i f_i fi​

• 对于一个新的点，我们已知其斜率，我们需要：

  • 求出第一个碰到的点
  • 求出新个点的 $x,y$
  • 将新的点加入图中

• 由于 x = s u m j x=sum_j x=sumj​ , k = 2 ∗ c i = 2 ∗ ( s u m i − a ) k=2*c_i=2*(sum_i-a) k=2∗ci​=2∗(sumi​−a)，两者均单调递增

• 因此记 k i k_i ki​ 第一个碰到的点为 x p , y p x_p,y_p xp​,yp​ ，那么对于 k i + 1 k_{i+1} ki+1​ ，对于 $p$ 之前的点肯定不会作为 k i + 1 k_{i+1} ki+1​ 的第一个碰到的点

• 具体需要的操作：

  • 对于新来的 k i k_i ki​ ，求出第一个碰到的点以及 x i , y i x_i,y_i xi​,yi​，删除两点间斜率小于 k i k_i ki​ 的点
  • 由于 $x$ 单调递增，我们在结尾处插入 x i , y i x_i,y_i xi​,yi​ 同时维护住凸包的性质，即保证两点间斜率逐渐变大

• 考虑用单调队列维护

//定义，即上文所述
#define k(i) (2*(s[i]-a))
#define y(i) (f[i] + s[i]*s[i])
#define x(i) (s[i])

//单调队列部分
	for(int i=1;i<=n;i++)
    {
        while(head<tail && (q[head] 与 q[head+1] 之间的斜率 < k(i)) )
            head++;
        f[i] = calc(i, q[head]); // 队首即为第一个碰到的点
        while(head<tail && (i 与 q[tail-1] 间斜率 小于等于 i 与 q[tail] 之间的斜率 )
            tail--;
        q[++tail] = i;
    }

判断 (q[head] 与 q[head+1] 之间的斜率 是否小于 k(i))：
bool cmp1(int p,int q,int i)
{
	return (y(q)-y(p)) < k(i) * (x(q)-x(p));	
}

while(head<tail && cmp1(q[head],q[head+1],i))
		head++;

判断 i 与 q[tail-1] 间斜率 是否小于等于 i 与 q[tail] 之间的斜率：
bool cmp2(int i,int j1,int i2,int j2)
{
    return (y(j1)-y(i1))*(x(j2)-x(i2)) >= (y(j2)-y(i2))*(x(j1)-x(i1));
}

while(head<tail && cmp2(i,q[tail-1],i,q[tail]))
		tail--;
		

#include <iostream>
#define int long long
using namespace std;
const int MAXN=2e5+5;
int n,a,head,tail,s[MAXN],f[MAXN],q[MAXN];
#define k(i) (2*(s[i]-a))
#define y(i) (f[i] + s[i]*s[i])
#define x(i) (s[i])
bool cmp1(int p,int q,int i)
{
	return (y(q)-y(p)) < k(i) * (x(q)-x(p));	
}
bool cmp2(int i1,int j1,int i2,int j2)
{
    return (y(j1)-y(i1))*(x(j2)-x(i2)) >= (y(j2)-y(i2))*(x(j1)-x(i1));
}
int calc(int i,int j)
{
    return f[j]+(s[i]-s[j]-a)*(s[i]-s[j]-a);
}
signed main()
{
    cin>>n>>a;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i]; 
		s[i] += s[i-1];
    }
    for(int i=1;i<=n;i++)
    {
        while(head<tail && cmp1(q[head],q[head+1],i)) head++;
        f[i] = calc(i, q[head]);
        while(head<tail && cmp2(i,q[tail-1],i,q[tail])) tail--;
        q[++tail] = i;
    }
    cout<<f[n]<<endl;
}

例题：任务安排1

推出方程后稍微改写一下即可

• 此题 $x,k$ 也均为单调递增

#include <iostream>
#define int long long
using namespace std;
const int MAXN=2e5+5;
int n,s,head,tail,T[MAXN],F[MAXN],g[MAXN],q[MAXN];
#define k(i) (s+T[i])
#define y(i) (g[i])
#define x(i) (F[i])
bool cmp1(int p,int q,int i)
{
	return (y(q)-y(p)) < k(i) * (x(q)-x(p));	
}
bool cmp2(int i1,int j1,int i2,int j2)
{
    return (y(j1)-y(i1))*(x(j2)-x(i2)) >= (y(j2)-y(i2))*(x(j1)-x(i1));
}
int calc(int i,int j)
{
   	return g[j] + T[i]*F[i] - T[i]*F[j] + s*F[n] - s*F[j];
}
signed main()
{
    cin>>n>>s;
    for(int i=1;i<=n;i++)
    {
        cin>>T[i]>>F[i]; 
		T[i] += T[i-1];
		F[i] += F[i-1];
    }
    for(int i=1;i<=n;i++)
    {
        while(head<tail && cmp1(q[head],q[head+1],i)) head++;
        g[i] = calc(i, q[head]);
        while(head<tail && cmp2(i,q[tail-1],i,q[tail])) tail--;
        q[++tail] = i;
    }
    cout<<g[n]<<endl;
}

例题：任务安排2

• 此题和上一题一样但是这里的 T i T_i Ti​ 可能为负数,因此 $k$ 不一定单调递增

• 这时我们就不能利用单调性在单调队列中弹出斜率比当前 k i k_i ki​ 小的元素了,因为后面的 k i k_i ki​ 第一个碰到的点可能在这些元素之中

• 但由于凸包斜率单调递增的特性,我们可以考虑在队列中二分找出 k j − 1 , j < k i < k j , j + 1 k_{j-1,j}< k_i< k_{j,j+1} kj−1,j​<ki​<kj,j+1​ 的 $j$ ,即为第一个碰到的点

bool cmp1(int p,int q,int i)
{
	return (y(q)-y(p)) < k(i) * (x(q)-x(p));	
}
// 二分查找 k[j-1,j]<k[i]<k[j,j+1] 的点
int search(int l,int r,int target)
{
	while(l<=r-5)
	{
		int mid=(l+r)>>1;
		if(cmp1(q[mid],q[mid+1],target)) l=mid;
		else r=mid;
	}
	for(int i=l;i<=r;i++)
		if(!cmp1(q[i],q[i+1],target)) return q[i];
}

#include <iostream>
#define int long long
using namespace std;
const int MAXN=3e5+5;
int n,s,head,tail,T[MAXN],F[MAXN],g[MAXN],q[MAXN];
#define k(i) (s+T[i])
#define y(i) (g[i])
#define x(i) (F[i])
bool cmp1(int p,int q,int i)
{
	return (y(q)-y(p)) < k(i) * (x(q)-x(p));	
}
bool cmp2(int i1,int j1,int i2,int j2)
{
    return (y(j1)-y(i1))*(x(j2)-x(i2)) >= (y(j2)-y(i2))*(x(j1)-x(i1));
}
int calc(int i,int j)
{
	return g[j] + T[i]*F[i] - T[i]*F[j] + s*F[n] - s*F[j];
}
int search(int l,int r,int target)
{
	while(l<=r-5)
	{
		int mid=(l+r)>>1;
		if(cmp1(q[mid],q[mid+1],target)) l=mid;
		else r=mid;
	}
	for(int i=l;i<=r;i++)
		if(!cmp1(q[i],q[i+1],target)) return q[i];
}
signed main()
{
    cin>>n>>s;
    for(int i=1;i<=n;i++)
    {
        cin>>T[i]>>F[i]; 
		T[i] += T[i-1];
		F[i] += F[i-1];
    }
    for(int i=1;i<=n;i++)
    {
        int j = search(head,tail,i);
        g[i] = calc(i, j);
        while(head<tail && cmp2(i,q[tail-1],i,q[tail])) tail--;
        q[++tail] = i;
    }
    cout<<g[n]<<endl;
}