斜率优化第一题！ HDU3507 | 单调队列优化DP

放一手原题

题解：

第一次写（抄）斜率优化，心里还是有点小激动的。讲一下怎么实现的！

首先我们可以考虑一个朴素的dp：DP[i]表示前i个数字的最少花费，显然我们有一个转移方程

DP[i]=min{DP[j]+M+(sum[i]-sum[j])^2}

但是N^2肯定会超时，我们考虑优化他

假设有k<j<i，如果令j对i的贡献比k好

显然我们有这样的式子

DP[j]+M+(sum[i]-sum[j])^2 < DP[k]+M+(sum[i]-sum[j])^2

把平方打开之后移项

可以得到

(（DP[j]+sum[j]^2）- (DP[k]+sum[k]^2) ) / 2*(sum[j]-sum[k]) < sum[i]

可以把这个式子看成（yj - yk）/（xj - xk）这样就得到了一个类似斜率的式子！

有了这些结论有什么用呢？

令G[i,j]表示刚刚的斜率式，依然有k<j<i

当j的决策比k优秀的时候，则满足G[i,j]>G[j,k]

我们可以用单调队列维护解集，利用斜率判断元素的入队和出队，这样可以使时间复杂度降低到O(n)了

#include<cstdio>

#include<algorithm>

#include<cstring>

#define N 500005

using namespace std;

int dp[N],q[N],sum[N],l,r,n,m;

int GetDp(int i,int j)

{

    return dp[j]+m+(sum[i]-sum[j])*(sum[i]-sum[j]);

}

int GetUp(int j,int k)

{

    return dp[j]+sum[j]*sum[j]-(dp[k]+sum[k]*sum[k]);

}

int GetDown(int j,int k)

{

    return *(sum[j]-sum[k]);

}

int main()

{

    while (scanf("%d%d",&n,&m)!=EOF)

    {

        for (int i=,x;i<=n;i++)

            scanf("%d",&x),sum[i]=sum[i-]+x;

        l=r=;

        q[r++]=;

        for (int i=;i<=n;i++)

        {

            while (l+<r && GetUp(q[l+],q[l])<=sum[i]*GetDown(q[l+],q[l]))

                l++;

            dp[i]=GetDp(i,q[l]);

            while (l+<r && GetUp(i,q[r-])*GetDown(q[r-],q[r-])<=GetUp(q[r-],q[r-])*GetDown(i,q[r-]))

                r--;

            q[r++]=i;

        }

        printf("%d\n",dp[n]);

    }

    return ;

}

巴特西

斜率优化第一题！ HDU3507 | 单调队列优化DP

最新文章

热门文章