斜率优化

 

在被坑爹的斜率优化虐了1week之后。。终于出头了o(∩_∩)o…哈哈

 

在思考了一个晚上要怎么纪念悲剧的结束之后-写了一下这个boring的thing
——————————————————————————————————————–

1010: [HNOI2008]玩具装箱toy

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 2506  Solved: 834
[Submit][Status][Discuss]

 

 

 

 

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

——————————————————————————————————————–
上面是一个经典的斜率优化题目。。
为了突出斜率优化的优势 不妨设n<=1000000~
此时nlgon就一边去吧~~
经过深思熟虑 不难得出本题的O(N^2)的方程:f[i]=min(f[j]+(c[i]-c[j]-L-1)^2)
其中 f[i]表示前i个玩具放完的最小$$
       c[i]=前i个玩具长的和+i
为什么这样定义?、因为如果直接用前i个玩具长的和的话 j+1~i 塞在一堆表示是c[i]-c[j]+i-j-1
so麻烦啊
so。。。
然后吧方程化开 =f[j]+(c[i]-1-L)^2+c[j]^2-2*c[i]*c[j]+2*c[j]+2*L*c[j];
再把所有项里跟j完全无关的都干掉(因为那些对于判断哪个j比较优没影响)
=>   f[j]+c[j]^2-2*c[i]*c[j]+2*c[j]+2*L*c[j]
<你不干掉也nothing。。但是还是干掉好。。。>
再把所有只和j有关的项扔在一起:
 f[j]+c[j]^2+2*c[j]+2*L*c[j]     -2*c[i]*c[j]
然后把只和j有关的项扔在一起的设为y , y=f[j]+c[j]^2+2*c[j]+2*L*c[j]
再设呢个有i有j的项里的和j有关的东西设为x,x=c[j]
然后~  f[i]=y-2*c[i]*x
       =>y=2*c[i]*x+f[i]
对于每个点i有一个在坐标系上的坐标(c[i],f[i]+c[i]^2+2*c[i]+2*L*c[i])
因为斜率(2*c[i])单调上升所以可以用单调队列维护一个凸壳(方程取min的是维护下凸壳  max为上)
判断head能不能用的方法就是:
对于现在的i可以设有一个斜率为2*c[i]的直线从灰常灰常远的地方灰了过来
 第一个切到那个凸壳的时刻 切到凸壳的那个角的值就是对于这个i最优的j
然后f[i]就可以出来啦~~~
怎么判断时候切到呢 先把队列的head和队列的head+1比较:
把斜率2*c[i]带入两个点 分边求出一个b(即为y=2*c[i]*x+f[i]中的f[i])
比较其大小 如图:psb
显然绿(head)的b>蓝(head+1)的b
下一个点同理
但是只要一到切点 就。。。。

psb (1)

 

蓝>绿~~~~

而且对于i上升 i的斜率也会上升 所以他们切那个凸壳的切点只会越来越后面
也就是对于前面删除的点 后面不用在考虑了~
最后一步是维护凸壳 相当于加入一个坐标(c[i],f[i]+c[i]^2+2*c[i]+2*L*c[i])
再把 i tail tail-1三个判断:向量tail -> i 指向 向量tail-1 -> tail的左或右
对于下凸壳 左就说明是凸壳 右就不是 要dec(tail)
对于上凸壳反之.
CODE:
 
#include <cstdio>
const int maxn=200005;
long long team[maxn],f[maxn],c[maxn],y[maxn];
bool work(int i,int j,int k)
{
  if (y[j]-2*c[i]*c[j]>y[k]-2*c[i]*c[k]) return true;else return false;
}
// 判断直线和凸壳的切点
//这段程序在别的程序各种变形都是差不多的 只是我们判断的方法不一样 结果是一样的~
bool del(int i,int j,int k)
{
  if ((c[j]-c[k])*(y[i]-y[j])-(c[i]-c[j])*(y[j]-y[k])<0) return true;
  else return false;
}
//维护凸壳
//向量的叉乘? 好像是叫这个 。。。
int main()
{
freopen(“bzoj1010.in”,”r”,stdin);
freopen(“bzoj1010.out”,”w”,stdout);
  int n;long long l;
  scanf(“%d%I64d”,&n,&l);
  for (int i=1;i<=n;i++)
  {
    scanf(“%I64d”,&c[i]);
    c[i]+=c[i-1];
  }
  int h=0;int t=0;
  //一开始让h=t可以让队列的第一个值代表j=0(就是全部玩具在一起) 就不用特判了
  for (int i=1;i<=n;i++) c[i]+=i;
  for (int i=1;i<=n;i++)
  {
    while (h<t && work(i,team[h],team[h+1])) h++;
    int j=team[h];
    f[i]=f[j]+(c[i]-c[j]-l-1)*(c[i]-c[j]-l-1); //team[h]直接就是对于i的最优解了
    y[i]=f[i]+c[i]*c[i]+2*c[i]*(l+1);
    while (h<t && del(i,team[t],team[t-1])) t–;
    t++;
    team[t]=i;
  }
  printf(“%I64d”,f[n]);
fclose(stdin);fclose(stdout);
}
ps:如果斜率不是递增的也是可以做的 但是要nlogn就是了 而且据说极其麻烦= =。。
 
再次ps:如果斜率递减就反过来做 就递增了~  注意维护凸包那里会不一样!<被这个坑了很久 …..>

发表评论