BZOJ1010【HNOI2008】玩具装箱toy <斜率优化>

Problem

【HNOI2008】玩具装箱toy

Description

教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。教授有编号为的件玩具，第件玩具经过压缩后变成一维长度为.为了方便整理，教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说如果将第件玩具到第个玩具放到一个容器中，那么容器的长度将为制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为,其制作费用为.其中是一个常量。教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过。但他希望费用最小.

Input

第一行输入两个整数.接下来行输入.

Output

输出最小费用.

Sample Input

Sample Output

标签：斜率优化DP

Solution

令，有如下方程：。

预处理。对于当前到的位置，必然存在，使得

按照此斜率维护单调栈即可。

Code

#include <bits/stdc++.h>
#define MAX_N 50000
using namespace std;
typedef double dnt;
typedef long long lnt;
template <class T>
inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, l, sta[MAX_N+5], s, t;	lnt f[MAX_N+5], w[MAX_N+5];
dnt calc(int p, int q) {return (f[p]-f[q]+(w[p]+l)*(w[p]+l)-(w[q]+l)*(w[q]+l))/(2.0*(w[p]-w[q]));}
int main() {
    read(n), read(l), l++;
    for (int i = 1; i <= n; i++) read(w[i]), w[i] += w[i-1];
    for (int i = 1; i <= n; i++) w[i] += i;
    for (int i = 1; i <= n; i++) {
        while (s < t && calc(sta[s+1], sta[s]) <= w[i]) s++;
        f[i] = f[sta[s]]+(w[i]-w[sta[s]]-l)*(w[i]-w[sta[s]]-l);
        while (s < t && calc(sta[t], sta[t-1]) > calc(i, sta[t])) t--;
        sta[++t] = i;
    }
    return printf("%lld", f[n]), 0;
}