Duanyll's Blog

洛谷P3195 [HNOI2008]玩具装箱TOY

13 April 2019 | Duanyll | Tags: OI 题解 DP

经典的一道斜率优化DP,很久以前写的,现在再拿出来复习一下

简单读题可以得出本题的DP方程是

\[dp[i] = min(dp[j]+(sum[i]-sum[j] + i - j - 1 - L)^2)\]

但是这样转移的复杂度高达$O(n^2)$,5e4的数据不能接受,需要优化.

为了简便计算,令$s[i]=sum[i]+i,C=L+1$.

\[dp[i] = dp[j] + (s[i]-s[j]-C)^2\]

假设存在决策$j$和$k$($1\leq j < k < i$),使得$k$比$j$更优,则有

\[dp[j] + (s[i]-s[j]-C)^2 \geq dp[k] + (s[i]-s[k]-C)^2\]

展开式子得

\[dp[j] + s[i]^2 - 2*s[i]*(s[j] + C) + (s[j] + C)^2 \geq dp[k] + s[i]^2 - 2*s[i]*(s[k] + C) + (s[k] + C)^2\]

移项

\[2*s[i]*(s[k] - s[j]) \geq dp[k]-dp[j] + (s[k]+C)^2-(s[j]+C)^2\]

把变量$s[k],s[j]$除过去

\[2*s[i] \geq \frac{dp[k]-dp[j] + (s[k]+C)^2-(s[j]+C)^2}{s[k] - s[j]}\]

为了看得更清楚,再令$h[i]=(s[i]+C)^2$

\[2*s[i] \geq \frac{dp[k]+h[k] - dp[j]-h[j]}{s[k] - s[j]}\]

经过这样的变换,这个DP方程就有了个斜率样子了:如果把$dp[j]+h[j]$看做纵坐标,把$s[j]$看做横坐标,那么$2*s[i]$就是过这两点的直线的斜率.

再重申一遍,只要满足上面这个式子(考虑每一个i时,左侧是一个常量!),决策k就比决策j更优.

由于$2*s[i]$是单调递增的,所以如果我们把$(s[j],dp[j]+h[j])$对应的点依次绘制在坐标系上,就会构成一个函数(随便想一个函数的图像).每当我们将一个点从右侧连接到这个图像上是,就可以知道它与上一个点之间的斜率,再比较上上个点与上一个点的斜率,如果这两个斜率是递减的,说明当前决策一定更有可能比上一个决策最优!

这像不像一个单调队列?我们已经有了进队的条件了,可以维护一个优秀程度递增(在j递增的基础上)的单调队列了.

那么出队呢?很好的是,$2s[i]$也是单调递增的.所以我们只要把当前看起来不会更优的点(队首斜率大于$2s[i]$时)出队,让当前可以更优的点成为队首.

所以像这样能用单调队列解决的关键点:

  1. 能把两个决策点优劣的关系式化成斜率式
  2. 式子左边对i具有单调性
  3. 式子右边视作x坐标的项对j具有单调性
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

typedef long long int64;
const int MAXN = 50050;

int64 a[MAXN];
int64 n,L;
int64 sum[MAXN],s[MAXN],h[MAXN];
int64 que[MAXN];
int64 dp[MAXN];

double cal(int j,int k){
    return (double)(dp[k]-dp[j] + h[k]-h[j])/(s[k] - s[j]);
}

int main(){
    cin >> n >> L;
    for(int i = 1;i<=n;i++){
        cin >> a[i];
        sum[i] = sum[i-1] + a[i];
        s[i] = sum[i] + i;
        h[i] = (s[i]+L+1) * (s[i]+L+1);
    }
    h[0] = (L+1) * (L+1);
    int head = 0,tail = 0;
    for(int i = 1;i<=n;i++){
        while(head < tail && cal(que[head],que[head+1]) <= 2*s[i]){
            head++;
        }
        dp[i] = dp[que[head]] + (s[i]-s[que[head]]-L-1)*(s[i]-s[que[head]]-L-1);
        while(head < tail && cal(que[tail],i) < cal(que[tail-1],que[tail])){
            tail--;
        }
        que[++tail] = i;
    }
    cout << dp[n] << endl;
}