学步园

关于斜率优化，这篇论文讲得很好：周源 浅谈数形结合思想在信息学竞赛中的应用

思路借鉴了这篇博客：[HNOI2008] 玩具装箱toy - 智障 - 博客频道 - CSDN.NET

但是公式是不唯一的哦~

dp[i]表示打包到玩具i所需最小费用，dp[i] = min{dp[j] + (sum[i] - sum[j] + i - j - 1 - l) ^ 2}

令 y1[i] = sum[i] + i, y2[i] = sum[i] + i + 1 + l
则原表达式可转化为 dp[i] = min{dp[j] + (y1[i] - y2[j]) ^ 2}

设i之前的检查点j和k(j > k)，则j比k更优的条件是：
dp[j] + (y1[i] - y2[j]) ^ 2 <= dp[k] + (y1[i] - y2[k]) ^ 2

即转化为：
(dp[j] + y2[j] ^ 2) - (dp[k] + y2[k] ^ 2) <= 2 * y1[i] * (y2[j] - y2[k])

令w[i] = dp[i] + y2[i] ^ 2
w[j] - w[k] <= 2 * y1[i] * (y2[j] - y2[k])

然而y2[i]是单增的，于是两边同除(y2[j] - y2[k]),即
(w[j] - w[k]) / (y2[j] - y2[k]) <= 2 * y1[i]

其中y1[i]又是递增的，于是可以用单调队列维护一个下凸线，每次只检查队首元素。

#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
using namespace std;
#define EPS 1e-8
#define MAXN 50010
#define LL long long

int n, l;
int head, tail;
int q[MAXN];
LL c[MAXN], w[MAXN];
LL dp[MAXN], sum[MAXN], y1[MAXN], y2[MAXN];

inline double r(int j, int k)
{
    w[j] = dp[j] + y2[j] * y2[j];
    w[k] = dp[k] + y2[k] * y2[k];
    return 1.0 * (w[j] - w[k]) / (1.0 * (y2[j] - y2[k]));
}

int main()
{
//    freopen("1010.in", "r", stdin);

    while(~scanf("%d%d", &n, &l))
    {
        y1[0] = sum[0] = 0;
        y2[0] = 1 + l;
        for(int i = 1; i <= n; i++)
        {
            scanf("%lld", c + i);
            sum[i] = sum[i - 1] + c[i];
            y2[i] = sum[i] + i + 1 + l;
            y1[i] = sum[i] + i;
        }

        head = tail = q[0] = w[0] = 0;
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i++)
        {
            while((head < tail) && (r(q[head + 1], q[head]) <= 2.0 * y1[i]))
                head++;// cout << head << endl;
            dp[i] = dp[q[head]] + (LL)(y1[i] - y2[q[head]]) * (y1[i] - y2[q[head]]);
            while((head < tail) && (r(q[tail], q[tail - 1]) >= r(i, q[tail])))
                tail--;
            q[++tail] = i;
        }
        printf("%lld\n", dp[n]);
    }
}