文章目录

斜率优化学习笔记

发布于 2022-09-12

斜率单调，决策点单调

使用单调队列维护凸包。

题意

给定 $n, a, b, c$，和一个长度为 $n$ 的数组 $z$。
定义 $i$ 到 $j$ 这一段的价值：
$$X = \sum\limits_{k = i}^j z_k$$
则价值为：
$$C = a \cdot X^2 + b \cdot X + c$$
我们要把数组分成若干个段，求所有段的价值和的最大值。
$1 \leq n \leq 10^6, -5 \leq a \leq -1, -10^7 \leq b, c \leq 10^7, 1 \leq z_i \leq 100$

题解

首先，定义 $S\left(l, r\right) = \sum\limits_{i = l}^r z_i$。
则 $\mathcal O\left(n^2\right)$ 的转移方程为：
$$f\left(i\right) = \min_{j = 0}^{i - 1} \left\{f\left(j\right) + a \cdot {S\left(j + 1, i\right)}^2 + b \cdot S\left(j + 1, i\right) + c\right\}$$

// Please submit with C++14! It's best to use C++20 or higher version.
#ifndef LOCAL        // Spectre
#pragma region HEAD  // By rbtree (https://rbtr.ee)
#endif
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstring>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>
#ifdef ___RB_DEBUG___
#include "rb_debug.h"
#else
#define dbg(...)
#endif
#define ra (scanf("%lld", &la), la)
#define LIKELY(exp) __builtin_expect(bool(exp), 1)
#define UNLIKELY(exp) __builtin_expect(bool(exp), 0)
#define ai(arr, value) __inia<decltype(arr)::value_type>(value)

template <typename _Tp>
_Tp __inia(typename _Tp::value_type __Val = _Tp::value_type()) {
  _Tp __target;
  return __target.fitp(__Val), __target;
}

typedef long long tp;
tp la;
using namespace std;
#ifndef LOCAL
#pragma endregion HEAD
#endif

////////////////////////////////////////////////////////////////////////////////

constexpr tp Hat_N = 1e6 + 3;

signed main() {
  tp n = ra, a = ra, b = ra, c = ra;
  array<tp, Hat_N> z, p, f;
  for_each(&z[1], &z[n] + 1, [](tp& v) { v = ra; });
  f.fill(-(-1ull >> 2));
  f[0] = p[0] = 0;
  for (tp i = 1; i <= n; ++i) {
    p[i] = p[i - 1] + z[i];
  }
  for (tp i = 1; i <= n; ++i) {
    for (tp j = 0; j < i; ++j) {
      tp t = p[i] - p[j];
      f[i] = max(f[i], f[j] + a * t * t + b * t + c);
    }
  }
  printf("%lld\n", f[n]);
  return 0;
}

////////////////////////////////////////////////////////////////////////////////

接下来，考虑斜率优化。

设 $S\left(i\right) = \sum\limits_{j = 1}^i z_i$

判断队首是否合法：
如果 $j$ 比 $k$ 优，则
$$f\left(j\right) + a \cdot \left(S\left(i\right) - S\left(j\right)\right)^2 + b \cdot \left(S\left(i\right) - S\left(j\right)\right) + c > f\left(k\right) + a \cdot \left(S\left(i\right) - S\left(k\right)\right)^2 + b \cdot \left(S\left(i\right) - S\left(k\right)\right) + c$$
整理得：
$$S\left(i\right) > \frac{f\left(k\right) - f\left(j\right) + a \cdot S\left(k\right)^2 - a \cdot S\left(j\right) + b \cdot S\left(j\right) - b \cdot S\left(k\right)}{2a \cdot \left(S\left(j\right) - S\left(k\right)\right)}$$
构造直线解析式（$y = k \cdot x + b$）：
我们把最优化的信息表示为 $b$，也就是截距，则移项得 $b = y - k \cdot x$。
把只与 $j$ 有关的表示为 $y$。算出
$$ k = 2a \cdot S\left(i\right) \\ x = S\left(j\right) \\ b = f\left(i\right) - a \cdot S\left(i\right)^2 - b \cdot S\left(i\right) - c \\ y = f\left(i\right) + a \cdot S\left(i\right)^2 - b \cdot S\left(i\right) $$

用单调队列维护上凸包。

代码

// Please submit with C++14! It's best to use C++20 or higher version.
#ifndef LOCAL        // Spectre
#pragma region HEAD  // By rbtree (https://rbtr.ee)
#endif
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstring>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>
#ifdef ___RB_DEBUG___
#include "rb_debug.h"
#else
#define dbg(...)
#endif
#define ra (scanf("%lld", &la), la)
#define LIKELY(exp) __builtin_expect(bool(exp), 1)
#define UNLIKELY(exp) __builtin_expect(bool(exp), 0)
#define ai(arr, value) __inia<decltype(arr)::value_type>(value)

template <typename _Tp>
_Tp __inia(typename _Tp::value_type __Val = _Tp::value_type()) {
  _Tp __target;
  return __target.fitp(__Val), __target;
}

typedef long long tp;
tp la;
using namespace std;
#ifndef LOCAL
#pragma endregion HEAD
#endif

////////////////////////////////////////////////////////////////////////////////

tp a, b, c;

#define k(i) (2 * a * z[i])
#define x(i) z[i]
#define b(i) (f[i] - a * z[i] * z[i] - b * z[i] - c)
#define y(i) (f[i] + a * z[i] * z[i] - b * z[i])
#define slope(i, j) (1. * (y(i) - y(j)) / (x(i) - x(j)))

constexpr tp Hat_N = 1e6 + 3;

signed main() {
  tp n = ra;
  list<tp> s({0});
  array<tp, Hat_N> z, f;
  a = ra;
  b = ra;
  c = ra;
  f[0] = z[0] = 0;
  for_each(&z[1], &z[n] + 1, [](tp& v) { v = *(&v - 1) + ra; });
  for (tp i = 1; i <= n; ++i) {
    while (s.size() > 1 && slope(s.front(), *next(s.begin())) > k(i)) {
      s.pop_front();
    }
    f[i] =
        -(k(i) * x(s.front()) - y(s.front()) - a * z[i] * z[i] - b * z[i] - c);
    while (s.size() > 1 &&
           slope(*next(s.rbegin()), s.back()) <= slope(s.back(), i)) {
      s.pop_back();
    }
    s.push_back(i);
  }
  printf("%lld\n", f[n]);
  return 0;
}

////////////////////////////////////////////////////////////////////////////////

斜率单调，决策点不单调

使用单调队列维护凸包，然后在凸包上二分决策点。

题意

有 $n$ 个需要依次处理的任务，每个任务有完成所需时间 $t$ 和代价 $c$，可以将这些任务分成若干组。每组的代价定义为：
$$s + t \cdot \sum\limits_{i = l}^r c_i$$
，其中 $s$ 是一个给定的常量，$t$ 是这组任务完成的时间。
求最小的代价。
$1 \leq n \leq 3 \times 10^5, 1 \leq s \leq 2^8, -2^8 \leq t_i \leq 2^8, 0 \leq c_i \leq 2^8$

题解

首先，定义 $S\left(l, r\right) = \sum\limits_{i = l}^r c_i$
$f\left(i\right)$ 表示完成到第 $i$ 个任务所花费的最短时间。则
$$f\left(i\right) = \min\limits_{j = 0}^{i - 1} \left\{f\left(j\right) + s \cdot S\left(j, n\right) + z_i \cdot S\left(j, i\right)\right\}$$
，$z_i$ 表示 $\sum\limits_{j = 1}^i t_i$

// Please submit with C++14! It's best to use C++20 or higher version.
#ifndef LOCAL        // Spectre
#pragma region HEAD  // By rbtree (https://rbtr.ee)
#endif
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstring>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>
#ifdef ___RB_DEBUG___
#include "rb_debug.h"
#else
#define dbg(...)
#endif
#define ra (scanf("%lld", &la), la)
#define LIKELY(exp) __builtin_expect(bool(exp), 1)
#define UNLIKELY(exp) __builtin_expect(bool(exp), 0)
#define ai(arr, value) __inia<decltype(arr)::value_type>(value)

template <typename _Tp>
_Tp __inia(typename _Tp::value_type __Val = _Tp::value_type()) {
  _Tp __target;
  return __target.fitp(__Val), __target;
}

typedef long long tp;
tp la;
using namespace std;
#ifndef LOCAL
#pragma endregion HEAD
#endif

////////////////////////////////////////////////////////////////////////////////

signed main() {
  tp n = ra, s = ra;
  vector<tp> t(n + 1, 0), c(n + 1, 0), f(n + 1, -1ull >> 2);
  f[0] = 0;
  for (tp i = 1; i <= n; ++i) {
    t[i] = t[i - 1] + ra;
    c[i] = c[i - 1] + ra;
  }
  for (tp i = 1; i <= n; ++i) {
    for (tp j = 0; j < i; ++j) {
      f[i] = min(f[i], f[j] + s * (c[n] - c[j]) + t[i] * (c[i] - c[j]));
    }
  }
  printf("%lld\n", f[n]);
  return 0;
}

////////////////////////////////////////////////////////////////////////////////

接下来，考虑斜率优化。

设 $S\left(i\right) = \sum\limits_{j = 1}^i c_j$

直接构造直线解析式：

$$ y = f\left(j\right) \\ k = s + S\left(i\right) \\ x = S\left(j\right) \\ b = f\left(i\right) - s \cdot S\left(n\right) - z_i \cdot S\left(j\right) $$

此时决策点不单调，所以二分决策点。

注意，此题卡精度。
为了好理解，不考虑精度问题的代码也给出：

// Please submit with C++14! It's best to use C++20 or higher version.
#ifndef LOCAL        // Spectre
#pragma region HEAD  // By rbtree (https://rbtr.ee)
#endif
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstring>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>
#ifdef ___RB_DEBUG___
#include "rb_debug.h"
#else
#define dbg(...)
#endif
#define ra (scanf("%lld", &la), la)
#define LIKELY(exp) __builtin_expect(bool(exp), 1)
#define UNLIKELY(exp) __builtin_expect(bool(exp), 0)
#define ai(arr, value) __inia<decltype(arr)::value_type>(value)

template <typename _Tp>
_Tp __inia(typename _Tp::value_type __Val = _Tp::value_type()) {
  _Tp __target;
  return __target.fill(__Val), __target;
}

typedef long long tp;
tp la;
using namespace std;
#ifndef LOCAL
#pragma endregion HEAD
#endif

////////////////////////////////////////////////////////////////////////////////

#define x(i) c[i]
#define y(i) f[i]
#define k(i) (s + t[i])
#define slope(i, j) (1. * (y(j) - y(i)) / (x(j) - x(i)))

tp s;

vector<tp> t, c, f;
deque<tp> ch({0});

tp fd(double s) {
  tp l = 0, r = ch.size() - 2, tar = -1;
  while (l <= r) {
    tp mid = l + r >> 1;
    if (tp mid = l + r >> 1; slope(ch[mid], ch[mid + 1]) >= s) {
      r = mid - 1;
      tar = mid;
    } else {
      l = mid + 1;
    }
  }
  return ~tar ? ch[tar] : ch.back();
}

signed main() {
  tp n = ra;
  s = ra;
  t = c = vector<tp>(n + 1, 0);
  f.resize(n + 1, -1ull >> 2);
  f[0] = 0;
  for (tp i = 1; i <= n; ++i) {
    t[i] = t[i - 1] + ra;
    c[i] = c[i - 1] + ra;
  }
  for (tp i = 1; i <= n; ++i) {
    tp j = fd(k(i));
    f[i] = f[j] + s * (c[n] - c[j]) + t[i] * (c[i] - c[j]);
    while (ch.size() >= 2 &&
           slope(*next(ch.rbegin()), ch.back()) >= slope(ch.back(), i)) {
      ch.pop_back();
    }
    ch.push_back(i);
  }
  printf("%lld\n", f[n]);
  return 0;
}

////////////////////////////////////////////////////////////////////////////////

解決卡精度问题也很简单，我们不用除法了，移一下项，用乘法。

代码

// Please submit with C++14! It's best to use C++20 or higher version.
#ifndef LOCAL        // Spectre
#pragma region HEAD  // By rbtree (https://rbtr.ee)
#endif
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstring>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>
#ifdef ___RB_DEBUG___
#include "rb_debug.h"
#else
#define dbg(...)
#endif
#define ra (scanf("%lld", &la), la)
#define LIKELY(exp) __builtin_expect(bool(exp), 1)
#define UNLIKELY(exp) __builtin_expect(bool(exp), 0)
#define ai(arr, value) __inia<decltype(arr)::value_type>(value)

template <typename _Tp>
_Tp __inia(typename _Tp::value_type __Val = _Tp::value_type()) {
  _Tp __target;
  return __target.fill(__Val), __target;
}

typedef long long tp;
tp la;
using namespace std;
#ifndef LOCAL
#pragma endregion HEAD
#endif

////////////////////////////////////////////////////////////////////////////////

#define x(i) c[i]
#define y(i) f[i]
#define k(i) (s + t[i])
#define yc(i, j) (y(j) - y(i))
#define xc(i, j) (x(j) - x(i))

tp s;

vector<tp> t, c, f;
deque<tp> ch({0});

tp fd(double s) {
  tp l = 0, r = ch.size() - 2, tar = -1;
  while (l <= r) {
    tp mid = l + r >> 1;
    if (tp mid = l + r >> 1;
        yc(ch[mid], ch[mid + 1]) >= s * xc(ch[mid], ch[mid + 1])) {
      r = mid - 1;
      tar = mid;
    } else {
      l = mid + 1;
    }
  }
  return ~tar ? ch[tar] : ch.back();
}

signed main() {
  tp n = ra;
  s = ra;
  t = c = vector<tp>(n + 1, 0);
  f.resize(n + 1, -1ull >> 2);
  f[0] = 0;
  for (tp i = 1; i <= n; ++i) {
    t[i] = t[i - 1] + ra;
    c[i] = c[i - 1] + ra;
  }
  for (tp i = 1; i <= n; ++i) {
    tp j = fd(k(i));
    f[i] = f[j] + s * (c[n] - c[j]) + t[i] * (c[i] - c[j]);
    while (ch.size() >= 2 &&
           yc(*next(ch.rbegin()), ch.back()) * xc(ch.back(), i) >=
               yc(ch.back(), i) * xc(*next(ch.rbegin()), ch.back())) {
      ch.pop_back();
    }
    ch.push_back(i);
  }
  printf("%lld\n", f[n]);
  return 0;
}

////////////////////////////////////////////////////////////////////////////////

斜率不单调，决策点单调

由于此时斜率不单调，所以使用平衡树，按斜率进行排序。这样问题就转化为了“斜率单调，决策点单调”。

好像没找到这样的题目。。。

斜率不单调，决策点不单调

平衡树上二分即可。

题意

有金卷 A 和 B，它们每天的价值都可能会变。
每天，你可以进行两种操作：
卖出金券
卖出相同多的 A 卷和 B 卷。
买入金券
在第 $i$ 天，按照 $A : B = R_i : 1$ 买入 A 卷和 B 卷。
初始有 $s$ 元钱。
求第 $n$ 天最多能获得多少钱。
$1 \leq n \leq 10^5$

分类：学习笔记
最后更新于：2024-06-30 01:47:41^UTC+8
标签：动态规划优化斜率优化

2 条评论

sb_yyds · 2022-09-16 14:20

Orz

回复
DengDuck · 2022-09-14 19:22

Orz

回复

红黑树的小屋

斜率优化学习笔记

发布于 2022-09-12

斜率单调，决策点单调

题意

题解

代码

斜率单调，决策点不单调

题意

题解

代码

斜率不单调，决策点单调

斜率不单调，决策点不单调

题意

2 条评论

sb_yyds · 2022-09-16 14:20

DengDuck · 2022-09-14 19:22

发表评论

斜率优化 学习笔记

发布于 2022-09-12

斜率单调，决策点单调

题意

题解

代码

斜率单调，决策点不单调

题意

题解

代码

斜率不单调，决策点单调

斜率不单调，决策点不单调

题意

2 条评论

sb_yyds · 2022-09-16 14:20

DengDuck · 2022-09-14 19:22

发表评论

斜率优化学习笔记