[BZOJ1010] [HNOI2008] 玩具装箱toy (斜率优化)

Description

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

Input

  第一行输入两个整数N,L.接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7

Output

  输出最小费用

Sample Input

5 4
3
4
2
1
4

Sample Output

1

HINT

Source

Solution

  设$f[i]$表示前$i$个物品装箱所需最小花费。

  假设我们把$[j+1,i]$的物品装到一个箱子里,那么很容易得出dp方程:

  $f[i]=min\{f[j]+(i-j+(\sum_{k=j+1}^{i}c[k])-L)^{2}\}$

  现在要把这个$O(n^{2})$优化成$O(n)$:

  设$d[i]=d[i-1]+c[i]+1$,$P=L+1$,那么

  $f[i]=min\{f[j]+(d[i]-d[j]-P)^{2}\}$

  假设k<j<i,且j比k优,则:

  $f[j]+(d[i]-d[j]-P)^{2}<f[k]+(d[i]-d[k]-P)^{2}$

  化简后的结果是:

  $\frac{(f[j]+d[j]^{2})-(f[k]+d[k]^{2})}{d[j]-d[k]}<2*(d[i]-P)$

  将$f[j]+d[j]^{2}$看成$y_{j}$,将$d[j]$看成$x_{j}$,就变成了斜率的表达式。

  维护一个下凸壳($min$就是下凸壳,$max$就是上凸壳),找凸包上关于斜率$2*(d[i]-P)$的切点,该店就是决策点。

  说右凸壳的都给我狗带!狗带!!!

  由于满足决策单调性,所以决策$j$是单调不下降的,我们可以把多余的斜率删掉。

 #include <bits/stdc++.h>
using namespace std;
long long f[], c[];
int q[]; double pow(long long x)
{
return 1.0 * x * x;
} double slope(int x)
{
return (f[q[x]] + pow(c[q[x]]) - f[q[x - ]] - pow(c[q[x - ]])) / (c[q[x]] - c[q[x - ]]);
} int main()
{
int n, l, front = , back;
cin >> n >> l;
for(int i = ; i <= n; ++i)
{
cin >> c[i];
c[i] += c[i - ] + ;
}
++l;
q[back = ] = ;
for(int i = ; i <= n; ++i)
{
while(front + < back && slope(front + ) <= * (c[i] - l))
++front;
int j = q[front + ];
f[i] = f[j] + (long long)pow(c[i] - c[j] - l);
q[++back] = i;
while(front + < back && slope(back - ) >= slope(back))
q[--back] = i;
}
cout << f[n] << endl;
return ;
}
上一篇:flume+sparkStreaming实例 实时监控文件demo


下一篇:获取JSON格式的树形