P3195 [HNOI2008]玩具装箱TOY(斜率优化入门)

hhz6830975

2018-01-18 14:07:54

Solution

这是一道经典的斜率优化入门题,就用这题来作个总结好了 前言:斜率优化的思想其实和高中数学的线性规划有相似之处,因此建议没学过的同学先了解一下线性规划 首先提一下单调队列优化: 当dp方程为$dp[i]=a[i]+b[j]$时,这个方程是$O(n^2)$的 这时用单调队列可以将其优化为$O(n)$,具体方法这里不再赘述 而dp方程为$dp[i]=a[i] \cdot b[j]+c[i]+d[j]$时,由于存在$a[i] \cdot b[j]$这个既有$i$又有$j$的项,以上方法就不适用了,这时就需要使用斜率优化 回到本题,设前缀和为$sum[i]$,由题意易得dp方程: $$dp[i]=min(dp[j]+(sum[i]+i-sum[j]-j-L-1)^2) (j<i)$$ 但这个方程是$O(n^2)$的,显然不满足要求,因此需要进行优化 (以下称两点斜率为$slope(A,B)$) 令$a[i]=sum[i]+i$,$b[i]=sum[i]+i+L+1$(这一步是为了简化计算) 则 $$dp[i]=dp[j]+(a[i]-b[j])^2$$ 展开得 $$dp[i]=dp[j]+a[i]^2-2 \cdot a[i] \cdot b[j]+b[j]^2$$ 移项得 $$2 \cdot a[i] \cdot b[j]+dp[i]-a[i]^2=dp[j]+b[j]^2$$ 将$b[j]$看作$x$,$dp[j]+b[j]^2$看作$y$,这个式子就可以看作一条斜率为$2 \cdot a[i]$的直线 而对于每个$i$来说,$a[i]$都是确定的 接下来的步骤和线性规划很相似 $dp[i]$的含义转化为:当上述直线过点$P(b[j],dp[j]+b[j]^2)$时,直线在$y$轴的截距加上$a[i]^2$(一个定值) 而题目即为找这个截距的最小值 因此,类似线性规划,我们将这条直线从下往上平移,直到过一个符合要求的点时停下,此时截距即为最小 画出图像如下(红色为目标直线) ![](https://cdn.luogu.com.cn/upload/pic/13267.png) 结合图像分析可知,本题中可能为最优的$P$点(图中用直线连接)组成了一个下凸包(其他题目可能不同,结合图像具体分析) 显然,凸包中相邻两点斜率是单调递增的 而目标直线的斜率$2 \cdot a[i]$也是单调递增的 由图像又易知,满足条件的最优$P_j$为第一个$slope(P_j,P_{j+1}) > 2 \cdot a[i]$的点 因此,我们用单调队列维护这个凸包: 设队首为$head$,队尾为$tail$ 1. 对队首: $$while(slope(P_{head},P_{head+1})<2 \cdot a[i])\quad head++$$ 2. 此时队首的点即为最优,根据它计算出$dp[i]$ 3. 对队尾: $$while(slope(P_{tail-1},P_{tail})>slope(P_{tail-1},P_i)\quad tail--$$ 4. 在队尾插入$P_i$ 解释: 若$slope(P_j,P_{j+1})<2 \cdot a[i]$,显然$P_j$不是最优通过步骤1删去 因为目标直线斜率单调递增,所以当前删去的$P_j$一定对之后的$dp[i]$也不是最优,不会造成影响 而操作3的理由如下: ![](https://cdn.luogu.com.cn/upload/pic/13443.png) 图中红色的点为$P_i$ 显然,满足操作3的要求时,$P_{tail}$在凸包内部,一定不是最优,因此可以删去 以上即为本题算法 要注意,初始化时要加入单调队列的点为$P_0$而不是$P_1$(否则就变成了第一个物品必须单独装) 代码: ```cpp #include <iostream> #include <cstdio> #include <cstring> using namespace std; typedef double db; typedef long long LL; const int maxn=50010; int n,L; db sum[maxn],dp[maxn]; int head,tail,Q[maxn]; inline db a(int i){return sum[i]+i;} inline db b(int i){return a(i)+L+1;} inline db X(int i){return b(i);} inline db Y(int i){return dp[i]+b(i)*b(i);} inline db slope(int i,int j){return (Y(i)-Y(j))/(X(i)-X(j));} int main(){ scanf("%d%d",&n,&L); for(int i=1;i<=n;i++){ scanf("%lf",&sum[i]); sum[i]+=sum[i-1]; } head=tail=1; for(int i=1;i<=n;i++){ while(head<tail&&slope(Q[head],Q[head+1])<2*a(i)) ++head; dp[i]=dp[Q[head]]+(a(i)-b(Q[head]))*(a(i)-b(Q[head])); while(head<tail&&slope(i,Q[tail-1])<slope(Q[tail-1],Q[tail])) --tail; Q[++tail]=i; } printf("%lld\n",(LL)dp[n]); return 0; } ```