一类DP优化

对于一切形如 \(dp[i]=\max\{f_1(j)\times g_1(i)+f_2(j)\}+g_2(i)\) 的状态转移方程，

设 \(L_j(x)=f_1(j)x+f_2(j)\) 那么就有 \(dp[i]=max\{L_j(g_1(i))\}+g_2(i)\)。

从几何角度来看，只需要求出一些直线和 \(x=g_1(i)\) 交点的纵坐标的最大值。

李超线段树

利用李超线段树可以很好地维护上述信息。

李超线段树就是支持 \(O(\log N)\) 插入直线和查询 \(\max{L_i(x)}\) 的数据结构。

线段树的每个节点保存 \(L(mid)\) 最大的那条直线。

插入一条直线时，比较 \(L_{old}(mid)\) 和 \(L_{new}(mid)\)，较大者保留，较小者继续递归。

#define ls o << 1
#define rs o << 1 | 1
struct Line {
  int k, b;
  inline int func(int x) {
    return k * x + b;
  }
} t[N << 2];
void ins(int o, int l, int r, Line x) {
  int mid = l + r >> 1;
  bool lf = t[o].func(l) < x.func(l);
  bool ri = t[o].func(r) < x.func(r);
  bool mi = t[o].func(mid) < x.func(mid);
  if (mi) std::swap(x, t[o]);
  if (l == r || lf == ri) return;
  lf != mi ? ins(ls, l, mid, x) : ins(rs, mid + 1, r, x);
}
int ask(int o, int l, int r, int x) {
  int mid = l + r >> 1;
  if (x == mid) return t[o].func(x);
  return x <= mid ? ask(ls, l, mid, x) : ask(rs, mid + 1, r, x);
}

凸壳

还是从几何角度来看，我们实际上需要维护一个下凸壳。

如果 \(g_1(i)\) 和 \(f_1(j)\) 有单调性，那么可以用单调队列/单调栈来维护，相当于传统的斜率优化。

不满足单调性时，可以套上CDQ分治，每一层直接排序让他满足单调性。

一类DP优化

原文：https://www.cnblogs.com/HolyK/p/13920857.html