P3195 玩具装箱TOY
枫林晚
2018-04-27 12:08:21
#### 题目大意：
有n个数，要将他们分成若干段，每一段的cost定义为：
cost=r-l+ΣCk (k∈[r,l])
该段的最终花费是：(cost-L)^2;
给出L,n,C(1~n)，总共的最小花费。
#### 分析：
dp方程极容易想出来：
f[i]=max(f[j]+(sum[i]-sum[j]+i-j-1-L)^2)
其中sum[i]表示c(1~i)的和。因为取的这一段数从j+1开始，所以i-j-1（题目中i-j并不是区间长度！没有再加1）
O(n^2)直接挂掉。
因为状态O(n)已经非常不错，无法再优化了。所以考虑能不能优化转移的O(n)。
将表达式展开：
f[i]=f[j]+(sum[i]-sum[j]+i-j-1-L)^2
令a[k]=sum[k]+k;x[k]=a[k]+1+
f[i]=f[j]+(a[i]-x[j])^2
f[i]=f[j]+x[j]^2-2a[i]x[j]+a[i]^2
对于给定的i，a[i]^2是一个定值，所以当做常数先不用管，**但是记得最后加上！**
令y[k]=f[k]+x[k]^2;
f[i]=y[j]-2a[i]x[j]
移项：
**y[j]**=2a[i]**x[j]**+f[i]
对于给定的i,我们需要循环所有的j。
对于一个j,我们已经知道了x[j],y[j]。
将它看作一个点，所有的j构成一个点集，横坐标x[j],纵坐标y[j]
而对于给定的i，2a[i]是一个定值，看做斜率，而目标f[i]则是截距，所以要在j的点集之中找到一个点使得这条直线截距最小，本质是将y=2a[i]x的直线平移。
可以发现这些最优解的点必定在边界上。并且发现，斜率是单增的，而x一定也是单增的。所以可以维护一个左上下凸壳。
因为斜率单增，所以若一个点此时不是最优解，那么以后一定也不是最优解，可以直接从头pass掉；每次新增一个点，都要保证这是一个凸包，通过斜率要来从尾pass掉。
所以可以用单调队列维护！单调，在这里是指队列中的元素，每相邻两个元素所代表的点连成的线，其斜率是单调递增的。因为斜率都是正数，所以也就是画出来是一个左上凸包。
注意，**队列中至少要有一个0号元素不能出队**！这里第一个空位置是有意义的。否则就不存在线和斜率了。所以手写队列时，开始hd=tl=0,while判断中hd<tl 保证一定至少有一个元素，并且这个元素不会被其他元素替代。详见代码。
##### 具体步骤：
1.前缀和预处理
2.循环i，先删除队首，再更新答案，再更新队列。
3.输出f[n] GAME OVER
代码：
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=50000+10;
int n,L;
long long f[N];
long long sum[N];
int q[N],hd,tl;
long long a(int i)
{
return sum[i]+i;
}
long long x(int i)
{
return sum[i]+i+L+1;
}
long long y(int i)
{
return x(i)*x(i)+f[i];
}
double slope(int a,int b)
{
return ((double)y(b)-y(a))/((double)x(b)-x(a));
}//一堆函数
int t;
int main()
{
scanf("%d%d",&n,&L);
for(int i=1;i<=n;i++)
{
scanf("%d",&t);
sum[i]=sum[i-1]+t;
}
hd=0,tl=0;
for(int i=1;i<=n;i++)
{
while(hd<tl&&slope(q[hd],q[hd+1])<2*a(i)) hd++;//删除
f[i]=y(q[hd])-2*a(i)*x(q[hd])+a(i)*a(i);
while(hd<tl&&slope(q[tl-1],q[tl])>slope(q[tl-1],i)) tl--;
q[++tl]=i;//更新
}
printf("%lld",f[n]);
return 0;
}
```
#### 总结：
1.一个题能用斜率优化，必然能出现y=kx+b 线性形式，其中k是定值，x，y构成点集，b是目标值。
2.一个凸包能用单调队列优化的条件应该满足：
（1）查询的斜率单调
（2）插入的点横坐标有单调性
（否则要用平衡树、set）