模板——斜率优化

AubRain · 2018-06-02 19:50:36 · 个人记录

最近切了好几道紫牌斜率优化题，发现其实斜率优化真的不算难（不难敲，但挺难理解的），模板也非常明确。

首先把转移方程转换为以下形式：

然后只要填空就行了。

#include <bits/stdc++.h>
#define N 50005
#define int long long
using namespace std;

inline void read(int &X)
{
    X=0;int w=0;char ch=0;
    while(!isdigit(ch))w|=ch=='-',ch=getchar();
    while( isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    X=w?-X:X;
}

#define A(i) 
#define B(i)
#define C(i)
#define X(i) 
#define Y(i) (f[i]+B(i))
#define K(i,j) (double)(Y(i)-Y(j))/(X(i)-X(j))

int n,f[N];
int q[N],l=1,r=1;

void pop_front(int i){
    while(l<r and K(q[l],q[l+1])<=A(i)) l++;
}
void pop_back(int i){
    while(l<r and K(q[r],i)<=K(q[r-1],q[r])) r--;
}
void update(int i){
    int j=q[l];
    f[i]=Y(j)-A(i)*X(j)-C(i);
}
signed main()
{

  for(int i=1;i<=n;i++)
  {
    pop_front(i);
    update(i);
    pop_back(i);
    q[++r]=i;
  }
  printf("%lld\n",f[n]);
}

不过一般都要 long\; long 的，反正不差这点常数。

还有值得注意的就是，要考虑 X 是否严格单调，若不严格，计算斜率的时候 X 相等判一下 INF 就行了

此代码维护的是下凸壳，适用于求最小值，若要求最大值，只用把 pop 时的不等式方向变一下就行了。

注意：要根据查询斜率单调递增还是单调递减，确定维护左偏凸壳还是右偏凸壳。（总共有4种凸壳）