[HNOI2008]玩具装箱toy（斜率优化dp）

前言

这是我写的第一道$dp$斜率优化的题目，$dp$一直都很菜，而且咖啡鸡都说了这是基础的东西，然而看别人对$dp$斜率优化一大堆公式又看不懂就老老实实做几道题目，这个比较实在

描述

给出$n$和$l$.有$n$个玩具，第$i$个玩具的长度是$c[i]$，要求将玩具分成若干段，从$i$到$j$分为一段的长度为$x=j-i+sum_{k=i}^{j}c[k]$，费用为$(x-l)^{2}$. 求最小费用 [Link]

分析

用$dp[i]$表示前i个玩具所需的最小费用,则有

　　　　　　　　　　　　$dp[i]=minleft { dp[j]+(sum[i]-sum[j]+i-(j+1)-l)^{2}(1<=j<i) ight }$

其中$sum[i]$表示的是$c[i]$的前缀和.

为了方便,我们设

　　　　　　　　　　　　　　　　$A[i]=sum[i]+i,l=l+1$

于是原方程就等价于

　　　　　　　　　　　　$dp[i]=minleft{dp[j]+(A[i]−A[j]−l)^{2}(1<=j<i) ight}$

我们设$j<k<i$且在计算$dp[i]$的时候,决策k更优.也就是说

　　　　　　　　　　　　$dp[k]+(A[i]−A[k]−l)^{2}<dp[j]+(A[i]−A[j]−l)^{2}$

在纸上写写画画,把式子打开再变一下形,容易得到

　　　　　　　　　　　　$frac{[dp[k]+(A[k]+l)^{2}]-[dp[j]+(A[j]+l)^{2}]}{2 imes A[k]-2 imes A[j]}$ $<A[i]$

是不是很像

　　　　　　　　　　　　　　　　$frac{Y_{k}-Y_{j}}{X_{k}-X_{j}}$
的形式?

这玩意儿不就是斜率吗?!我们设它为$g(k,j)$

我们可以发现$A[i]$是单调递增的,所以所有决策可以转化为二维空间上的点集.

也就是说$k$这个点和j这个点的连线的斜率如果小于$A[i]$,那么$k$这个决策就更优.

那么对于三个决策$a<b<c$,如果有$g(c,b)<=g(b,a)$,那么$b$决策一定不会被选中.为什么呢?我们来讨论一下(对于任意$3<i<=n$):

1.如果$g(b,a)<A[i]$,那么必有$g(c,b)<A[i]$,也就是$c$最优,选择决策$c$.

2.如果$g(b,a)>=A[i]$,那么$b$不是最优,最优可能是$a$或$c$.

所以我们在新加入一个点的时候,就可以把它看作$c$,然后把所有这样的$b$都去掉,直到$g(c,b)>g(b,a)$，所以我们需要处理的斜率是单调递增的.

这样我们就可以用一个单调队列分别维护队首和队尾啦.

Code

#include <cstdio>
#define ll long long
#define Empty (head>=tail)
const int maxn = 5e4+10;
ll n, L, head, tail, j;
ll Q[maxn], sum[maxn], s[maxn], f[maxn];
inline double X(ll i) {return s[i];}
inline double Y(ll i) {return f[i]+(s[i]+L-1)*(s[i]+L-1);}
inline double Rate(ll i,ll k) {return (Y(k)-Y(i))/(X(k)-X(i));} 
int main()
{
    scanf("%lld%lld", &n, &L);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &sum[i]);
        sum[i] += sum[i-1], s[i] = sum[i]+i;
    }
    head = tail = 1; Q[1] = 0;
    for (int i = 1; i <= n; i++) {
        while(!Empty&&Rate(Q[head],Q[head+1])<2*s[i]) head++;
        j = Q[head]; f[i] = f[j]+(s[i]-s[j]-L-1)*(s[i]-s[j]-L-1);
        while(!Empty&&Rate(Q[tail-1],Q[tail])>Rate(Q[tail],i)) tail--;
        Q[++tail] = i;
    }
    printf("%lld
", f[n]);
}

View Code

网上讲了很多数形结合的方法，找截距最小，的确对理解很有帮助，但是可能像这样的对我来说更好理解，另外有些细枝末节的东西没有完全看懂，但是现在没必要纠结.

这里能用斜率优化是因为A[i]是单调的，至于具体为什么，先不细究

[HNOI2008]玩具装箱toy（斜率优化dp）

相关推荐