2023-03-15-1维DP四边形不等式优化(决策单调性优化)
对序列切割问题,令
若对所有
这是因为若四边形不等式满足,则
于是如果
那对于所有
(*)就是强化版决策单调性
令
那么
用
struct Info {
int l, r, pre;
} q[N];
struct Opt {
ll val, pre;
} f[N];
ll F(int j, int i) {
// 具体问题具体分析
}
int search(Info x, int i) {
int l = x.l;
int r = x.r;
int ans = r + 1;
while (l <= r) {
int mid = (l + r) / 2;
if (F(i, mid) <= F(x.pre, mid)) {
ans = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
return ans;
}
void DP() {
q[1] = (Info){1, n, 0};
int l = 1, r = 2;
for (int i = 1; i <= n; i++) {
while (q[l].r < i) l++;
int j = q[l].pre;
f[i] = (Opt){F(j, i), j};
q[l].l = i + 1;
if (q[l].r == i) l++;
while (l < r && F(i, q[r-1].l) <= F(q[r-1].pre, q[r-1].l)) r--;
int pos = i + 1;
if (l < r) {
pos = search(q[r-1], i);
q[r-1].r = pos - 1;
}
if (pos > n) continue;
q[r++] = (Info){pos, n, i};
}
printf("%lld\n", f[n].val);
}