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

Problem

【HNOI2008】玩具装箱toy

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;162\;MB}$

Description

$P$教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。$P$教授有编号为$1\sim 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$.
$1\le N\le50000,1\le L,C_i\le10^7$

Output

输出最小费用.

Sample Input

5 4
3
4
2
1
4

Sample Output

1

标签：斜率优化DP

Solution

令$L=L+1$，有如下$DP$方程：$f[i]=\min_{j=0}^{i-1}\{f[j]+[(i-j+\sum_{k=j}^{i}C_k)-L]^2\}$。

预处理$s[i]=\sum_{j=1}^{i}C_j,\;w[i]=s[i]+i$。对于当前$DP$到的位置$i$，必然存在$p,q\in[0,i)$，使得

$$\begin{aligned} f[p]+[(i-p+\sum_{k=p}^{i}C_k)-L]^2&\le f[q]+[(i-q+\sum_{k=q}^{i}C_k)-L]^2\\ &\Updownarrow\\ f[p]+(w[i]-w[p]-L)^2&\le f[q]+(w[i]-w[q]-L)^2\\ &\Updownarrow\\ f[p]+w[i]^2+w[p]^2+L^2-2\times w[i]&\times w[p]-2\times w[i]\times L+2\times w[p]\times L\\ &\le\\ f[q]+w[i]^2+w[q]^2+L^2-2\times w[i]&\times w[q]-2\times w[i]\times L+2\times w[q]\times L\\ &\Updownarrow\\ f[p]+(w[p]+L)^2-2\times w[i]\times w[p]&\le f[q]+(w[q]+L)^2-2\times w[i]\times w[q]\\ &\Updownarrow\\ \frac{(f[p]-f[q])+((w[p]+L)^2-(w[q]+L)^2)}{2\times(w[p]-w[q])}&\le w[i]\\ \end{aligned}$$

$$\therefore k(p,q)=\frac{(f[p]-f[q])+((w[p]+L)^2-(w[q]+L)^2)}{2\times(w[p]-w[q])}\le w[i]\iff p\;is\;better\;than\;q$$

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

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;
}