斜率优化

2 种方法

比如这个式子: (from [HNOI2008]玩具装箱TOY)

[f[i] = min{ f[j] + (sum[i] + i - sum[j] - j - L - 1) ^ 2 } ]

大概有两种方法:

考虑 (i, j) 的关系, 将分别只和 (i, j) 有关的式子分开,
整理成为 (y = kx + b) 的形式, 要求其中 (b) 为和 (f[i]) 有关的式子, (y) 是和 (f[j]) 有关的式子, (x) 和 (j) 有关, (k) 和 (i) 有关
这样一个 (j) 就成了一个坐标 ((x, y)), 本题中取 (min), 就转化成了在和 (i) 有关的斜率 (k) 下取最小的 (b) 即截距
考虑 (i) 的两个子状态 (j, k), 他们谁更优, 这里假定 (j > k), (j) 比 (k) 更优的情况
然后将 (j, k) 分别带入 (f[i]) 的递推式中, 同样将仅与 (j, k) 有关的式子分开, 整理为 (frac{y_j - y_k}{x_j - x_k} < k)
其中 (y) 是包含 (f) 的, (x) 不包含, (k) 则是仅与 (i) 有关, 取 (min) 就用 (<), 反之亦然

以上都是基本的转化, 现在考虑两种方法分别如何求最优值

首先都是要画图, 然后就会发现两种方法是极其类似的,

假设有 3 个可以取的点组成上凸折线, 由线性规划的方法容易得到, 用任何斜率取切, 中间那个上凸点都切不到, 会被另外两个点卡住
显然, 不管斜率如何, 都只需要留下下凸包的点
任然用这三个点, 首先左边两点的斜率 > 右边, 然后枚举一下现在的斜率与这两个的关系, 可以得到 3 中情况, 可以发现中间点都不用取
得到了同样的结论

于是, 对于每个 (i), 可以在 ([1, i - 1]) 这些点组成的凸包上的点取值, 用 (i) 的斜率一个一个比过去即可,
例如本题中保留下凸包, 对于两种方法, 都是找到第一个大于当前斜率的点

不难想到可以用二分来查找

然而, 许多题都满足 (i) 的斜率有单调性, 比如这题, 两种方法中斜率都是 (2(sum[i] + i)), 其中两个变量都是单增的, 所以单增
于是, 凸包中也是斜率不断增的, 对于每个 (i) , 把从凸包起点开始不断删(即上面的暴力过程), 直到大于当前斜率, 显然这样复杂度是线性的

接下来用本题具体演示一下

第一种:

设 (A[j] = (sum[j] + j + L + 1))

[f[j] + A[j] ^ 2 = 2 cdot (sum[i] + i) cdot A[j] + f[i] - (sum[i] + i) ^ 2 ]

第二种:

设 (A[j] = (sum[j] + j + L + 1))

[frac{(f[j] + A[j] ^ 2) - (f[k] + A[k] ^ 2)}{a[j] - a[k]} le 2 cdot (sum[i] + i) ]

代码是一样的


int n;

const int MAXN = 5e4 + 10;

LL L, sum[MAXN], a[MAXN], f[MAXN];

struct Node
{
    LL x, y;
} q[MAXN];
int h, t;

/*
0815
 */
int main()
{
    n = in();
    L = in();
    for (int i = 1; i <= n; ++ i) 
    {
	sum[i] = sum[i - 1] + in();
	a[i] = (sum[i] + i + L + 1);
    }
    a[0] = L + 1;
    f[0] = 0;
    h = t = 1;
    q[1].x = a[0], q[1].y = a[0] * a[0];
    for (int i = 1; i <= n; ++ i)
    {
	while (h < t && (q[h + 1].y - q[h].y) <= 2 * (sum[i] + i) * (q[h + 1].x - q[h].x)) ++ h;
	f[i] = q[h].y - 2 * (sum[i] + i) * q[h].x + (sum[i] + i) * (sum[i] + i);
	Node now = (Node) { a[i], f[i] + a[i] * a[i] };
	while (h < t && (now.y - q[t].y) * (q[t].x - q[t - 1].x) <= (q[t].y - q[t - 1].y) * (now.x - q[t].x)) -- t;
	q[++ t] = now;
    }
    printf("%lld
", f[n]);
    return 0;
}