P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为 1?N1\cdots N1?N 的 NNN 件玩具，第 iii 件玩具经过压缩后变成一维长度为 CiC_iCi? .为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说如果将第 iii 件玩具到第 jjj 个玩具放到一个容器中，那么容器的长度将为 x=j−i+∑k=ijCkx=j-i+\sum\limits_{k=i}^{j}C_kx=j−i+k=i∑j?Ck? 制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为 xxx ,其制作费用为 (X−L)2(X-L)^2(X−L)2 .其中 LLL 是一个常量。P教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过 LLL 。但他希望费用最小.输入格式：
第一行输入两个整数N，L.接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7
输出格式：
输出最小费用
5 4 3 4 2 1 4
输出样例#1： 复制
1
题解
这里
1 // luogu-judger-enable-o2 2 //minamoto 3 #include<iostream> 4 #include<cstdio> 5 #include<cstring> 6 #define db double 7 #define ll long long 8 using namespace std; 9 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 10 char buf[1<<21],*p1=buf,*p2=buf; 11 inline int read(){ 12 #define num ch-‘0‘ 13 char ch;bool flag=0;int res; 14 while(!isdigit(ch=getc())) 15 (ch==‘-‘)&&(flag=true); 16 for(res=num;isdigit(ch=getc());res=res*10+num); 17 (flag)&&(res=-res); 18 #undef num 19 return res; 20 } 21 const int N=50005; 22 int n,L; 23 db sum[N],dp[N];int h,t,q[N]; 24 inline db a(int i){return sum[i]+i;} 25 inline db b(int i){return sum[i]+i+L+1;} 26 inline db X(int i){return b(i);} 27 inline db Y(int i){return dp[i]+b(i)*b(i);} 28 inline db slope(int i,int j){return (Y(i)-Y(j))/(X(i)-X(j));} 29 int main(){ 30 //freopen("testdata.in","r",stdin); 31 n=read(),L=read(); 32 for(int i=1;i<=n;++i) sum[i]=read()+sum[i-1]; 33 h=t=1; 34 for(int i=1;i<=n;++i){ 35 while(h<t&&slope(q[h],q[h+1])<2*a(i)) ++h; 36 double p=a(i)-b(q[h]); 37 dp[i]=dp[q[h]]+p*p; 38 while(h<t&&slope(q[t-1],q[t])>slope(q[t-1],i)) --t; 39 q[++t]=i; 40 } 41 printf("%lld\n",(ll)dp[n]); 42 return 0; 43 }
「BZOJ1010」[HNOI2008] 玩具装箱toy（斜率优化）
原文：https://www.cnblogs.com/bztMinamoto/p/9544024.html