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。但他希望费用最小.

Solution

斜率优化的练习题。

\(F_i=\min ({f_j+(sum_i-sum_j+i-j-l-1)^2})\)

我们令 \(g_i=sum_i+l\)

若\(j<k\)，且决策\(k\)优于决策\(j\)

\(\frac{((f_k+(g_k+l+1)^2)-(f_j+(g_j+l+1))^2 )}{ (g_k - g_j)}<=2*f_i\)

Code 

#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define MN 50005int n,L;ll f[MN],g[MN];ll sqr(ll x){return x*x;}int que[MN],l=1,r=0;double calc(int j,int k){    return (double)(f[j]+sqr(g[j]+L)-f[k]-sqr(g[k]+L))/(double)(g[j]-g[k]);}void insert(int x){    for(;r>l&&calc(que[r],que[r-1])>=calc(x,que[r]);r--);    que[++r]=x;}int get(int x){    if(l>r) return 0;    for(;r>l&&calc(que[l+1],que[l])<=(double)2*g[x];l++);    return que[l];}int main(){    n=read();L=read()+1;    register int i,j;    for(i=1;i<=n;++i) g[i]=g[i-1]+read()+1;    f[0]=que[++r]=0;    for(i=1;i<=n;++i)    {        j=get(i);        f[i]=f[j]+sqr(g[i]-g[j]-L);        insert(i);    }    printf("%lld\n",f[n]);}
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！