斜率单调,决策点单调
使用单调队列维护凸包。
题意
给定 $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$
sb_yyds · 2022-09-16 14:20
Orz
DengDuck · 2022-09-14 19:22
Orz