斜率优化DP(转载）

转载自：

我们知道，有些DP方程可以转化成DP[i]=f[j]+x[i]的形式，其中f[j]中保存了只与j相关的量。这样的DP方程我们可以用单调队列进行优化，从而使得O(n^2)的复杂度降到O(n)。

可是并不是所有的方程都可以转化成上面的形式，举个例子：dp[i]=dp[j]+(x[i]-x[j])*(x[i]-x[j])。如果把右边的乘法化开的话，会得到x[i]*x[j]的项。这就没办法使得f[j]里只存在于j相关的量了。于是上面的单调队列优化方法就不好使了。

这里学习一种新的优化方法，叫做斜率优化，其实和凸包差不多，下面会解释。

举例子说明是最好的！HDU 3507，很适合的一个入门题。http://acm.hdu.edu.cn/showproblem.php?pid=3507

大概题意就是要输出N个数字a[N]，输出的时候可以连续连续的输出，每连续输出一串，它的费用是 “这串数字和的平方加上一个常数M”。

我们设dp[i]表示输出到i的时候最少的花费，sum[i]表示从a[1]到a[i]的数字和。于是方程就是：

dp[i]=dp[j]+M+(sum[i]-sum[j])^2；

很显然这个是一个二维的。题目的数字有500000个，不用试了，二维铁定超时了。那我们就来试试斜率优化吧，看看是如何做到从O(n^2)复杂度降到O(n)的。

分析:

我们假设k

两边移项一下，得到：(dp[j]+sum[j]^2-(dp[k]+sum[k]^2))/(2*(sum[j]-sum[k]))

那么不就是yj-yk/xj-xk

那么yj-yk/xj-xk

关键的来了：现在从左到右，还是设k

我们假设g[i,j]

如果g[i,j]>=sum[i]，那么j点此时是比i点要更优，但是同时g[j,k]>g[i,j]>sum[i]。这说明还有k点会比j点更优，同样排除j点。

排除多余的点，这便是一种优化！

接下来看看如何找最优解。

设k

由于我们排除了g[i,j]

这样，从左到右，斜率之间就是单调递减的了。当我们的最优解取得在j点的时候，那么k点不可能再取得比j点更优的解了，于是k点也可以排除。换句话说，j点之前的点全部不可能再比j点更优了，可以全部从解集中排除。

于是对于这题我们对于斜率优化做法可以总结如下：

1，用一个单调队列来维护解集。

2，假设队列中从头到尾已经有元素a b c。那么当d要入队的时候，我们维护队列的上凸性质，即如果g[d,c]=g[x,y]为止，并将d点加入在该位置中。

3，求解时候，从队头开始，如果已有元素a b c，当i点要求解时，如果g[b,a]

　　以下代码是我自己敲了一遍

#include
#include
#include
using namespace std;
int s[500005];
int dp[500005],q[500005];
int m,n;
int head,tail;
int getdp(int i,int j)
{
    return dp[j]+m+(s[i]-s[j])*(s[i]-s[j]);
}
int getup(int j,int k)     
{
    return dp[j]+s[j]*s[j]-(dp[k]+s[k]*s[k]);
}
int getdown(int j,int k)
{
    return 2*(s[j]-s[k]);
}
int main()
{
    while(scanf("%d%d",&n,&m)==2)
    {
        for(int i=1; i<=n; i++)scanf("%d",&s[i]);
        s[0]=dp[0]=0;
        for(int i=1; i<=n; i++)s[i]+=s[i-1];
        head=0,tail=0;
        q[tail++]=0;
        for(int i=1; i<=n; i++)
        {
            while(head+11],q[head])<=s[i]*getdown(q[head+1],q[head]))
                head++;
            /* head+1,个比head 更优，所以直排除head,让head++，至于之前的head，谁管他呢？这么菜， 还有脸留着浪费时间？*/
            dp[i]=getdp(i,q[head]);
            while(head+11])*getdown(q[tail-1],q[tail-2])<= getup(q[tail-1],q[tail-2])*getdown(i,q[tail-1]))
                tail--;
            /*说明  (tail-1 ,1)的决策比 (tail-2,~tail-1)更大，则说明，tail-1 是比tail-2更优的，
            而i是比tail更优的则，tail可以被排除了。tail--*/
            q[tail++]=i;
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}