[HNOI2008]玩具装箱（斜率优化入门）

题目描述

分析

先吐槽一波，为什么 latex 不能复制！！！！
好了让我们看看这道题。
设 $s_{i}$ 为前 $i$ 个玩具的长度前缀和，设 $f_{i}$ 表示前 $i$ 个玩具的最小费用，于是有一个显然的转移方程：
$f_{i} = m i n {f_{j - 1} + (i - j + s_{i} - s_{j - 1} - L)^{2}}$
然后我们令 $g (x) = s_{x} + x - L$ ， $t (x) = x + s_{x - 1}$
可以将转移方程化简为：
$f_{i} = m i n {f_{j - 1} + t (j)^{2} - 2 g (i) t (j)} + g (i)^{2}$
好了，来到这里，要开始进入斜率优化了！
令 $h (x) = f_{j - 1} + t (j)^{2}$
那么式子成为：
$f_{i} = m i n {h (j) - 2 g (i) t (j)} + g (i)^{2}$
我们做这一切完全是为了让式子好看一些（雾
既然叫优化，我们就不可能枚举每个点去转移，而是要快速得到决策点。
考虑 $j_{1} < j_{2}$ ， $j_{2}$ 比 $j_{1}$ 优的条件，注意下面中 $t (j_{2}) > t (j_{1})$ ，因为 $t (x)$ 单调增：
$h (j_{1}) - 2 g (i) t (j_{1}) > h (j_{2}) - 2 g (i) t (j_{2}) \Rightarrow h (j_{2}) - h (j_{1}) < 2 g (i) (t (j_{2}) - t (j_{1})) \Rightarrow \frac{h (j_{2}) - h (j_{1})}{t (j_{2}) - t (j_{1})} < 2 g (i)$
那部分是不是很像斜率的形式？所以称之为斜率优化。
记 $T (j_{1}, j_{2}) = \frac{h (j_{2}) - h (j_{1})}{t (j_{2}) - t (j_{1})}$
我们目前得到的结论：若 $j_{1} < j_{2}$ ， $T (j_{1}, j_{2}) < 2 g (i)$ 时， $j_{2}$ 更优。

下面是两个重要的结论

队列中相邻点的斜率都大于 $2 g (i)$ 时，决策点为队首。
因为 $T (j_{1}, j_{2}) > 2 g (i)$ ，因此 $j_{1}$ 优于 $j_{2}$ ，同理， $j_{2}$ 优于 $j_{3}$ ，以此类推。
队列中相邻点斜率单调增
让我们考虑 $j_{1} < j_{2} < j_{3}$ 这相邻三个点的情况： $j_{2}$ 要成为决策点，就必须满足存在 $g (i)$ :
- $j_{2}$ 比 $j_{1}$ 优，即 $T (j_{1}, j_{2}) < 2 g (i)$
- $j_{2}$ 比 $j_{3}$ 优，即 $T (j_{2}, j_{3}) > 2 g (i)$
于是有 $T (j_{1}, j_{2}) < 2 g (i) < T (j_{2}, j_{3})$ ，于是队列中斜率单调增。
知道了这个，就可以用一个单调队列来维护斜率了。

于是，我们用单调队列维护斜率单调增，同时队列中斜率都大于 $2 g (i)$ ，每次决策点在队首。
由于每个点只进出队列一次，所以总复杂度 $O (n)$

代码如下

#include <bits/stdc++.h>
#define N 50005
using namespace std;
typedef long long LL;
LL z = 1, L, s[N], f[N];
int q[N], x = 1, y;
LL t(int x){
	return s[x - 1] + x;
}
LL h(int x){
	return f[x - 1] + t(x) * t(x);
}
LL g(int x){
	return x + s[x] - L;
}
double T(int i, int j){
	return 1.0 * (h(i) - h(j)) / (t(i) - t(j));
}
int main(){
	int i, j, n, m;
	scanf("%d%d", &n, &L);
	for(i = 1; i <= n; i++) scanf("%d", &j), s[i] = s[i - 1] + j;
	for(i = 1; i <= n; i++){
		q[++y] = i;
		while(x + 1 < y && T(q[y - 1], q[y]) < T(q[y - 2], q[y - 1])) q[y - 1] = q[y], y--;
		while(x < y && T(q[x], q[x + 1]) < 2 * g(i)) x++;
		f[i] = f[q[x] - 1] + (g(i) - t(q[x])) * (g(i) - t(q[x]));
	}
	printf("%lld", f[n]);
	return 0;
}

[HNOI2008]玩具装箱 （斜率优化入门）

题目描述

分析

代码如下

[HNOI2008]玩具装箱（斜率优化入门）