对于状态转移方程含有变量与常量的乘积项,并满足某些性质的 DP 的一类优化。
例题:HNOI2008
显然,可以得到一个 DP 的式子:
令
直接对这个式子进行模拟,时间复杂度为
把这个 DP 式子当做一个方程,去掉
移项可以得到:
如果将
其中,
也就是说,对于每个点,都有一条斜率相同(为
这是一个线性规划的问题,也可以理解为有一条斜率为
有一个重要的结论,对于点
一个重要的性质是,对于任意三个点,如果这个点是上凸的(斜率递减),则中间那个点,无论平移的直线斜率如何,都不可能是第一个遇到的。
在感性的验证若干次后,可以从数学上证明这个重要的事实:
令三个点依次为
因为上凸,所以有:
假设当平移直线斜率为
则:
那么就应该有
与条件矛盾,故不存在这样的直线。
也就是说,可能的
换而言之,所有可能的决策集合,在该平面直角坐标系上形成下凸包。
维护这个凸包,及时排除无效决策点,这就是斜率优化,也被称为凸包优化(convex hull)。
除此之外,本题还有若干在斜率优化中不平凡的性质:
- 对于横坐标
s(j) ,随着j 的递增,s(j) 也是递增的。这意味着在依次考虑每一个决策点时,都是有序的。 - 对于每条平移直线的斜率
2 \times s(i) ,随着i 的递增,2 \times s(i) 也是递增的。这意味着,在凸包中,当相邻两个点的斜率小于2 \times s(i) ,靠左(横坐标更小)的点在今后的 “平移” 过程中永远不会再被交到应当可以及时删去这些点。
要维护这样一个凸包,涉及到在某一端,根据某个值的大小进行删除,删除,使得在整个序列中都有单调性。
这就是单调队列所擅长的事了。
入队时,根据该点,队首的斜率与队首,队次首的斜率的大小关系比较即可。
由于本题满足平移直线斜率递增,故可以当队尾的斜率小于当前平移直线斜率时,将其抛出。
具体见代码。
时间复杂度
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int MAXN = 5e4 + 10;
int n;
ll L, t[MAXN], f[MAXN];
int q[MAXN], l, r;
db Y(int i) { return 1.0 * t[i] * t[i] + f[i]; }
db X(int i) { return 1.0 * t[i]; }
db slope(int i, int j) { return (Y(i) - Y(j)) / (X(i) - X(j)); }
db G(int i) { return 2.0 * (t[i] - L); }
int main() {
scanf("%d %lld", &n, &L);
L ++;
for (int i = 1; i <= n; ++i) scanf("%lld", &t[i]);
for (int i = 1; i <= n; ++i) t[i] += t[i - 1];
for (int i = 1; i <= n; ++i) t[i] += i;
q[1] = 0;
l = 1, r = 1;
for (int i = 1; i <= n; ++i) {
while (l < r && slope(q[l], q[l + 1]) < G(i)) l ++;
int j = q[l];
f[i] = f[j] + (t[i] - t[j] - L) * (t[i] - t[j] - L);
while (l < r && slope(q[r], i) < slope(q[r - 1], q[r])) r --;
q[++ r] = i;
}
printf("%lld\n", f[n]);
return 0;
}
其他题与做法
[USACO08MAR]Land Acquisition G
横坐标单调递减,维护下凸包,斜率单调递减。
首先将所有满足
具体而言,以
令
写成斜率优化的样子:
发现斜率
把
就和例题一样的做法了。
时间复杂度
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
const int MAXN = 5e4 + 10;
int n;
struct node { ll w, l; bool operator <(const node& b) { return w == b.w ? l < b.l : w < b.w; } } arr[MAXN];
int stck[MAXN], top;
ll f[MAXN], w[MAXN], l[MAXN];
int q[MAXN], _l, _r;
db X(int i) { return 1.0 * l[i + 1]; }
db Y(int i) { return 1.0 * f[i]; }
db slope(int i, int j) { return 1.0 * (Y(i) - Y(j)) / (X(i) - X(j)); }
db G(int i) { return -1.0 * w[i]; }
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%lld %lld", &arr[i].w, &arr[i].l);
sort(arr + 1, arr + n + 1);
for (int i = 1; i <= n; ++i) {
while (top && arr[stck[top]].l <= arr[i].l) top --;
stck[++top] = i;
}
for (int i = 1; i <= top; ++i) w[i] = arr[stck[i]].w, l[i] = arr[stck[i]].l;
_l = _r = 1;
for (int i = 1; i <= top; ++i) {
while (_l < _r && slope(q[_l], q[_l + 1]) >= G(i)) _l ++;
int j = q[_l];
f[i] = f[j] + w[i] * l[j + 1];
while (_l < _r && slope(q[_r], q[_r - 1]) < slope(q[_r], i)) _r --;
q[++ _r] = i;
}
printf("%lld\n", f[top]);
return 0;
}
[APIO2010]特别行动队
横坐标单调递增,维护上凸包,斜率单调递减。
有 DP 转移式子:
其中,
写成斜率优化的样子:
要使纵截距最大,维护上凸包,题中
稍微有一点不一样,改一下大于小于号即可。
时间复杂度
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
const int MAXN = 1e6 + 10;
int n;
ll s[MAXN], f[MAXN], a, b, c;
db X(int i) { return 1.0 * s[i]; }
db Y(int i) { return 1.0 * (f[i] - b * s[i] + a * s[i] * s[i]); }
db slope(int i, int j) { return (Y(i) - Y(j)) / (X(i) - X(j)); }
db G(int i) { return 2.0 * a * s[i]; }
int q[MAXN], l, r;
int main() {
scanf("%d %lld %ld %lld", &n, &a, &b, &c);
for (int i = 1; i <= n; ++i) scanf("%lld", &s[i]), s[i] += s[i - 1];
l = r = 1; q[1] = 0;
for (int i = 1; i <= n; ++i) {
while (l < r && slope(q[l], q[l + 1]) > G(i)) l ++;
int j = q[l];
f[i] = f[j] + (s[i] - s[j]) * (s[i] - s[j]) * a + (s[i] - s[j]) * b + c;
while (l < r && slope(i, q[r]) > slope(q[r], q[r - 1])) r --;
q[++ r] = i;
}
printf("%lld\n", f[n]);
return 0;
}
[IOI2002]任务安排
横坐标单调递增,维护下凸包,斜率单调递增。
有一个很妙的方程:
其中,
这个方程妙在,将费用(开机费用)提前计算了,就不必要知道到底启动了几次。
写成斜率优化的样子:
维护下凸包,斜率单调递增,横坐标单调递增。
和例题一样的维护方法。
时间复杂度
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
const int MAXN = 1e4 + 10;
int n;
ll s, t[MAXN], c[MAXN], f[MAXN];
db X(int i) { return 1. * c[i]; }
db Y(int i) { return 1. * f[i]; }
db slope(int i, int j) { return (Y(i) - Y(j)) / (X(i) - X(j)); }
db G(int i) { return 1. * (t[i] + s); }
int q[MAXN], l, r;
int main() {
scanf("%d %lld", &n, &s);
for (int i = 1; i <= n; ++i) {
scanf("%lld %lld", &t[i], &c[i]);
t[i] += t[i - 1], c[i] += c[i - 1];
}
l = r = 1;
for (int i = 1; i <= n; ++i) {
while (l < r && slope(q[l], q[l + 1]) < G(i)) l ++;
int j = q[l];
f[i] = f[j] + t[i] * (c[i] - c[j]) + s * (c[n] - c[j]);
while (l < r && slope(q[r], q[r - 1]) > slope(q[r], i)) r --;
q[++r] = i;
}
printf("%lld\n", f[n]);
return 0;
}
[SDOI2016]征途
横坐标单调递增,维护下凸包,斜率单调递增。
比上面的题都不那么裸了。
令这
答案为:
则只需要求出最小的
考虑
令
有:
展开写成斜率优化的式子为;
要使截距最小,维护下凸包,斜率单调递增,横坐标单调递增。
对于每一个
还可以使用一下滚动优化,把第二维优化。
时间复杂度
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
const int MAXN = 3e3 + 10;
int n;
ll m, s[MAXN], sum, f[MAXN], g[MAXN];
db X(int i) { return 1.* s[i]; }
db Y(int i) { return 1.* (g[i] + s[i] * s[i]); }
db slope(int i, int j) { return (Y(i) - Y(j)) / (X(i) - X(j)); }
db K(int i) { return 2.* s[i]; }
int main() {
scanf("%d %lld", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%lld", &s[i]), sum += s[i], s[i] += s[i - 1];
for (int i = 1; i <= n; ++i) f[i] = INT_MAX;
for (int i = 1; i <= m; ++i) {
memcpy(g, f, sizeof f), memset(f, 0, sizeof f);
static int q[MAXN];
int l = 0, r = 0;
q[0] = q[1] = q[r] = 0;
for (int j = 1; j <= n; ++j) {
while (l < r && slope(q[l], q[l + 1]) < K(j)) l ++;
int k = q[l];
f[j] = g[k] + (s[j] - s[k]) * (s[j] - s[k]);
while (l < r && slope(q[r], q[r - 1]) > slope(q[r], j)) r --;
q[++ r] = j;
}
}
printf("%lld\n", m * f[n] - sum * sum);
return 0;
}
变种
斜率不单调
利用二分查找。
斜率不单调,则需维护整个凸包,每次转移的时候需要在单调队列(此时已经退化为单调栈)上二分。
具体而言,本题需要维护一个下凸包。则每次转移时二分找到第一个斜率大于
时间复杂度
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
const int MAXN = 3e5 + 10;
int n;
ll s, c[MAXN], t[MAXN], f[MAXN];
ll X(int i) { return c[i]; }
ll Y(int i) { return (f[i] - s * c[i]); }
//db slope(int i, int j) { return (Y(i) - Y(j)) / (X(i) - X(j)); }
ll K(int i) { return t[i]; }
ll deltaX(int i, int j) { return (X(i) - X(j)); }
ll deltaY(int i, int j) { return (Y(i) - Y(j)); }
int q[MAXN], l, r;
int find(ll g) {
int L = l, R = r - 1, ret = -1;
while (L <= R) {
int mid = (L + R) >> 1;
if (deltaY(q[mid + 1], q[mid]) < g * deltaX(q[mid + 1], q[mid])) L = mid + 1;
else ret = mid, R = mid - 1;
}
if (ret == -1) return q[r];
return q[ret];
}
int main() {
scanf("%d %lld", &n, &s);
for (int i = 1; i <= n; ++i) {
ll tt, cc;
scanf("%lld %lld", &tt, &cc);
t[i] = t[i - 1] + tt, c[i] = c[i - 1] + cc;
}
l = r = 1, q[1] = 0;
for (int i = 1; i <= n; ++i) {
int j = find(K(i));
f[i] = f[j] + t[i] * (c[i] - c[j]) + s * (c[n] - c[j]);
while (l < r && deltaY(q[r], q[r - 1]) * deltaX(i, q[r]) >= deltaY(i, q[r]) * deltaX(q[r], q[r - 1])) r --;
q[++ r] = i;
}
printf("%lld\n", f[n]);
return 0;
}