一道斜率优化dp题。
先考虑状态和转移方程：
令$dp[i]$表示装前$i$个玩具所需要最小花费，$j$表示上一个容器右端点，$sum[i]$表示前$i$个玩具长度之和，则可得到转移方程为： $$ dp[i]=\min_{0 \le j<i}\ dp[j] +(\ i-j-1+sum[i]-sum[j]-L\ )^2\ $$ 又令$\ f[i]=sum[i]+i \ $继续简化方程为： $$ dp[i]=\min_{0 \leq j<i}\ dp[j]+(\ f[i]-f[j]-(\ L+1\ )\ )^2 $$
但显然这样复杂度是$O(n^2)$的，对于$n\le5e4$是无法通过的。
再考虑优化：
对于$dp[i]$是由最优的$j$转移过来，假设现在有两个决策$j1,j2(0 \le j1<j2<i)$且$j2$优于$j1$，则有： $$ dp[j1]+(f[i]-f[j1]-(L+1))^2 \ge dp[j2]+(f[i]-f[j2]-(L+1))^2 $$ 拆开可得： $$ dp[j1]-2\times f[i]\times (f[j1]+L+1)+(f[j1]+L+1)^2 \ge dp[j2]-2\times f[i]\times (f[j2]+L+1)+(f[j2]+L+1)^2 $$ $$ 2\times f[i]\times (f[j2]-f[j1]) \ge dp[j2]+(f[j2]+L+1)^2-dp[j1]-(f[j1]+L+1)^2 $$ 令$g[i]=(f[i]+L+1)^2\ $则有： $$ 2\times f[i]\times (f[j2]-f[j1])\ge dp[j2]+g[j2]-dp[j1]-g[j1]$$ $$ 2\times f[i]\ge \frac{dp[j2]+g[j2]-dp[[j1]-g[j1]}{f[j2]-f[j1]} \\ $$若$j1,j2$满足上面这个式子，那么$j2$一定优于$j1$。观察发现，两两决策间的斜率是单调上升的。 因为：
发现上图中$j2$不可能是一个最优决策，当$2\times f[i]$小于$j1,j2$的斜率时，$j1$显然优于$j2$，而当$2\times f[i]$大于等于$j1,j2$斜率时，显然$j2,j3$的斜率更小也满足$j3$优于$j2$，所以$j2$不可能最优，也就是两两决策间斜率单调上升（也就是一个下凸壳）。
又因为这道题$f[i]$是单调上升的，所以我们可以用单调队列来维护。具体实现：把决策放进一个单调队列里，如果队首元素和第二个元素间的斜率小于等于当前的$2\times f[i]$，我们就把队首元素弹出（因为他不优），这样每次更新$i$时就用处理过后的单调队列队首元素即可。再向单调队列里加入$i$,如果发现加入$i$后队尾元素两两间斜率不满足单调上升，我们就先把队尾元素弹出，直到满足但满足单调上升后，再将$i$入队。
复杂度：$O(n)$
代码：
1 #include <bits/stdc++.h>
2
3 #define int long long
4
5 using namespace std;
6
7 int read(){
8 int x=0,fl=1;
9 char c=getchar();
10 while(!isdigit(c)){if(c=='-') fl=-1;c=getchar();}
11 while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
12 return x*fl;
13 }
14
15 const int N=5e4+5;
16
17 int n,L;
18 int c[N],sum[N],f[N],g[N];
19 int dp[N];
20 int q[N],head,tail;
21
22 double check(int j1,int j2){
23 return (double)(dp[j2]+g[j2]-dp[j1]-g[j1])/(f[j2]-f[j1]);
24 }
25
26 signed main(){
27 n=read(),L=read();
28 for(int i=1;i<=n;++i){
29 c[i]=read();
30 sum[i]=sum[i-1]+c[i];
31 f[i]=sum[i]+i;
32 g[i]=(f[i]+L+1)*(f[i]+L+1);
33 }
34 g[0]=(L+1)*(L+1);
35 for(int i=1;i<=n;++i){
36 while(head<tail&&check(q[head],q[head+1])<=2*f[i]) ++head;//队首元素不优，弹出队首元素
37 dp[i]=dp[q[head]]+(f[i]-f[q[head]]-L-1)*(f[i]-f[q[head]]-L-1);//更新dp值
38 while(head<tail&&check(q[tail],i)<check(q[tail-1],q[tail])) --tail;
39 q[++tail]=i;
40 }
41 cout<<dp[n]<<'\n';
42 return 0;
43 }
标签：P3195,元素,j1,j2,斜率,dp,HNOI2008,装箱,单调 From： https://www.cnblogs.com/qazxswedc123/p/17063952.html