Description

P 教授要去看奥运, 但是他舍不下他的玩具, 于是他决定把所有的玩具运到北京. 他使用自 己的压缩器进行压缩, 其可以将任意物品变成一堆, 再放到一种特殊的一维容器中. P 教授 有编号为 \(1, 2, \ldots, n\) 的 \(n\) 件玩具, 第 \(i\) 件玩具经过压缩后变成一维长度为 \(C_i\). 为了方便整理, P 教授要求在一个一维容器中的玩具编号是连续的. 同时如果一个 一维容器中有多个玩具, 那么两件玩具之间要加入一个单位长度的填充物, 形式地说如果将第 \(i\) 件玩具到第 \(j\) 个玩具放到一个容器中, 那么容器的长度将为 \(x=j-i+\sum_{k=i}^{j} C_k\).

制作容器的费用与容器的长度有关, 根据教授研究, 如果容器长度为 \(x\), 其制作费用为 \((x-L)^2\). 其中 \(L\) 是一个常量. P 教授不关心容器的数目, 他可以制作出任意长度的容 器, 甚至超过 \(L\), 但他希望费用最小.

Input

第一行输入两个整数 \(n, L\). 接下来 \(n\) 行输入 \(C_i\).

Output

输出一个整数, 表示最小费用.

Sample Input

5 4
3
4
2
1
4

Sample Output

1

Data Range

对于所有的数据, 满足:\(1 \leq n \leq 50000, 1 \leq L, C_i \leq 10^7\)

Explanation

如果不需要斜率优化直接暴力就可以了...... 但是这道题需要优化, 所以只能膜别人的题解了. 这里先膜一发黄学长的题解:

\[dp[i] = min(dp[j] + (sum[i] - sum[j] + i - j - 1 - L)^2) (j \lt i)\]

令 \(f[i] = sum[i] + i, c = L + 1\)

则 \(dp[i] = min(dp[j] + (f[i] - f[j] - c)^2)\)

1. 证明决策单调性

假设在状态 \(i\) 处的 \(k\) 决策优于 \(j\) 决策, 即:

\[dp[k] + (f[i] - f[k] - c)^2 \leq dp[j] + (f[i] - f[j] - c)^2\]

则对于 i 后的所有状态 t, 要证明决策单调性, 即证:

\[dp[k] + (f[t] - f[k] - c)^2 \leq dp[j] + (f[t] - f[j] - c)^2\]

\[\Leftarrow dp[k] + (f[i] + v - f[k] - c)^2 \leq dp[j] + (f[i] + v - f[j] - c)^2\]

\[\Leftarrow dp[k] + (f[i] - f[k] - c)^2 + 2 \cdot v \cdot (f[i] - f[k] - c) + v^2 \leq dp[j] + (f[i] - f[j] - c)^2 + 2 \cdot v \cdot (f[i] - f[j] - c) + v^2\]

\[\Leftarrow 2 \cdot v \cdot (f[i] - f[k] - c) \leq 2 \cdot v \cdot (f[i] - f[j] - c)\]

\[\Leftarrow f[k] \geq f[j]\]

由于以上结论显然, 证毕.

2. 求斜率方程

\[\because dp[k] + (f[i] - f[k] - c)^2 \leq dp[j] + (f[i] - f[j] - c)^2\]

\[\therefore dp[k] + f[i]^2 - 2 \cdot f[i] \cdot (f[k] + c) + (f[k] + c)^2 \leq dp[j] + f[i]^2 - 2 \cdot f[i] \cdot (f[j] + c) + (f[j] + c)^2\]

\[\therefore dp[k] - 2 \cdot f[i] \cdot (f[k] + c) + (f[k] + c)^2 \leq dp[j] - 2 \cdot f[i] \cdot (f[j] + c) + (f[j] + c)^2\]

\[\therefore \frac{ dp[k] + (f[k] + c)^2 - dp[j] - (f[j] + c)^2 }{ 2 \cdot (f[k] - f[j]) } \leq f[i]\]

\(f[i]\) 是单调递增的, 我们使用队列维护一个下凸壳, 每次取出队头作为决策

加入决策 \(i\) 时, 令队尾为 \(q[r]\), 前一个为 \(q[r - 1]\)

满足 \(slope(q[r], i) \lt slope(q[r - 1], q[r])\) 时, 显然队尾是无效的, 将其弹出

3. 相关论文

有关斜率优化的论文就看这里了:用单调性优化动态规划 (PDF版本)

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

// #define USE_BRUTE_FORCE_CODE
#define sqr(__x) ((lli)(__x)*(lli)(__x))
using namespace std;
typedef long long lli;
typedef long double llf;
const int maxn = 50010;
const lli infinit = 0x3f3f3f3f3f3f3f3fll;

int n, L, C[maxn];
lli sum[maxn], dp[maxn];
lli que[maxn];

llf slope(int j, int k) { return (dp[k] - dp[j] + sqr(sum[k] + L)
    - sqr(sum[j] + L)) / (2.0 * (sum[k] - sum[j])); }

int main()
{
    scanf("%d%d", &n, &L);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &C[i]);
        sum[i] = sum[i - 1] + C[i];
    }
    #ifdef USE_BRUTE_FORCE_CODE
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = infinit;
        for (int j = 0; j < i; j++) {
            // lli diff = sqr(sum[i] - sum[j] + i - j - 1 - L);
            lli diff = sqr((sum[i] + i) - (sum[j] + j) - (L + 1));
            dp[i] = min(dp[i], dp[j] + diff);
        }
    }
    #else
    // As though we need them
    for (int i = 1; i <= n; i++)
        sum[i] += i;
    L = L + 1; // New constant
    // Slope-optimized DP
    int l = 1, r = 0;
    que[++r] = 0;
    for (int i = 1; i <= n; i++) {
        while (l < r && slope(que[l], que[l + 1]) <= sum[i]) l++;
        int pos = que[l]; // Best.
        dp[i] = dp[pos] + sqr(sum[i] - sum[pos] - L);
        while (l < r && slope(que[r], i) < slope(que[r - 1], que[r])) r--;
        que[++r] = i;
    }
    #endif
    // Output results
    lli res = dp[n];
    printf("%lld\n", res);
    return 0;
}