「Note」斜率优化dp

斜率优化简单总结

优化原理

斜率优化基于单调队列/单调栈。
可以再 $O(1)$ 的时间复杂度内找到最优的状态。

如何优化

以Cats Transport一题为例。
首先设：
$d[i] = d[i - 1] + x$(即当前山与第一号山的距离)
$a[i] = t - d[h]$(能接到$i$号猫的最早出发时间)
$sum[i] = sum[i - 1] + a[i]$($a[]$的前缀和)
可以得到方程:
$$dp_{i,j} = min_{0 < k} ^{j-1}(dp_{i-1,k} + (j - k) * a_j - sum_j + sum_k)$$
时间复杂度为$pm^2$。
亲测30pts
那么导致时间复杂度增高的原因是在寻找最优的$k$时多跑了一重循环。
尝试去掉这重循环。。。
将原式子展开可以有:
$$dp_{i,j} = dp_{i-1,k} + (j - k) * a_j - sum_j + sum_k$$
假设有$k_1$、$k_2$两个状态点, $k_2$在$k_1$后，且$k_2$比$k_1$更优。
则可以知道:
$$dp_{i-1,{k_1}} + (j - k_1) * a_j - sum_j + sum_{k_1} \geq dp_{i-1,{k_2}} + (j - k_2) * a_j - sum_j + sum_{k_2}$$
化简:
$$dp_{i-1,{k_1}} + (j - k_1) * a_j + sum_{k_1} \geq dp_{i-1,{k_2}} + (j - k_2) * a_j + sum_{k_2}$$
将带有$i$的和没有的整理得：
$$ (dp_{i-1,{k_2}} + sum_{k_2}) - (dp_{i-1,{k_1}} + sum_{k_1}) \leq a_j \times (k_2 - k_1)$$
因为$k_2$在$k_1$后，所以$(k_2 - k_1) \geq 1$。
将$(k_2 - k_1)$移到左边:
$$ \frac{(dp_{i-1,{k_2}} + sum_{k_2}) - (dp_{i-1,{k_1}} + sum_{k_1})}{(k_2 - k_1)} \leq a_j$$
将$(dp_{i-1,k2},k_2)$看做一个点，可知此题应维护一个下凸壳。
于是套上板子即可。

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXP = 105;

int n, m, p;
int d[MAXN], sum[MAXN], a[MAXN], dp[MAXP][MAXN];
int head, tail, q[MAXN];

int Y(int id, int i) {
	return dp[id - 1][i];
}

int X(int i) {
	return i;
}

long double K(int id, int i, int j) {
	return double(Y(id, j) - Y(id, i)) / (X(j) - X(i));
}

int main() {
	scanf ("%d %d %d", &n, &m, &p);
	for (int i = 2, x; i <= n; i++) {
		scanf ("%d", &x);
		d[i] = d[i - 1] + x;
	}
	for (int i = 1, h, t; i <= m; i++) {
		scanf ("%d %d", &h, &t);
		a[i] = t - d[h];
	}
	sort (a + 1, a + 1 + m);
	for (int i = 1; i <= m; i++)
		sum[i] = sum[i - 1] + a[i];
	for (int i = 1; i <= p; i++) {
		head = 1, tail = 1, q[1] = 0;
		for (int j = 1; j <= m; j++) {
			while (K(i, q[head], q[head + 1]) <= a[j] && head < tail) head++;
			int k = q[head];
			dp[i][j] = dp[i - 1][k] + (j - k) * a[j] - sum[j] + sum[k];
			while (K(i, q[tail - 1], q[tail]) >= K(i, q[tail - 1], j)) tail--;
			q[++tail] = j;
		}
	}
	printf ("%d\n", dp[p][m]);
	return 0;
}