[HNOI2008]玩具装箱toy

Time Limit:1000MS  Memory Limit:165536K
Total Submit:204 Accepted:76

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

Source

额。。看了决策单调性之后决定A个一题，结果搞了半天，我太菜了555。。。
这是很基本的决策单调性，也可以用斜率优化来搞，不过单调性感觉比较直观，而且也能AC(*^__^*)
就是用一个双端队列来保存当前的决策区间，用二分查找寻分界点。。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<deque>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1;
const int maxn=50000+1;
typedef long long ll;
struct node
{
int l,r,ch;
node(){}
node(int _l,int _r,int _ch):l(_l),r(_r),ch(_ch){}
};
ll Sum[maxn]={0},Dp[maxn];
int top=0;
int L,n;
ll Cost(int l,int r)
{
ll x=Sum[r]-Sum[l-1]+r-l;
x-=L;
return x*x;
}
ll Get(int New,int Old)
{
if(Old>=New)return inf;
return Dp[Old]+Cost(Old+1,New);
}
int binary(node t,int i)
{
int l=t.l,r=t.r;
#define check(m) (Get(m,t.ch)<Get(m,i))
if(check(r)) return r;
while(l+1<r)
{
int m=(l+r)/2;
if(check(m)) l=m;
else r=m;
}
return l;
#undef check
}
void Init()
{
scanf("%d %d",&n,&L);
rep(i,n)scanf("%lld",Sum+i+1);
for(int i=1;i<=n;i++) Sum[i]+=Sum[i-1];
}
void Work()
{
Dp[0]=0;deque<node> D;
D.pb(node(1,n,0));
for(int i=1;i<=n;i++)
{
Dp[i]=Get(i,D.front().ch);
if(D.front().l<D.front().r)
D.front().l++;
else
D.pop_front();
node t;int e;
while(D.size())
{
t=D.back();
if(Get(t.l,i)<=Get(t.l,t.ch))
{
D.pop_back();
}
else
{
e=binary(t,i);
D.back().r=e;
break;
}
}
if(D.size()==0)
D.pb(node(i+1,n,i));
else if(e<n) D.pb(node(e+1,n,i));
}
cout<<Dp[n]<<endl;
}
int main()
{
//freopen("in","r",stdin);
Init();
Work();
}