HDU 3507 Print Article

dp斜率优化

题面链接

• 题意

  输出序列a[n]，每连续输出的费用是连续输出的数字和的平方加上常数M，让我们求这个费用的最小值。
  

• 输入

  输入n,m (0 ≤ n ≤ 500000, 0 ≤ M ≤ 1000)，接下来输入n个数

• 输出

  输出满足条件的最小值

• 样例

  Sample Input
  5 5
  5
  9
  5
  7
  5
  Sample Output
  230

• 分析（摘自博客园）

  设dp[i]表示输出前i个的最小费用，那么有如下的DP方程：
  dp[i]= min{ dp[j]+(sum[i]-sum[j])^2 +M } 0 其中 sum[i]表示数字的前i项和。
  相信都能理解上面的方程。
  直接求解上面的方程的话复杂度是O(n^2)
  对于500000的规模显然是超时的。下面讲解下如何用斜率优化DP使得复杂度降低一维。
  我们首先假设在算 dp[i]时，k 也就是
  dp[j]+(sum[i]-sum[j])^2+M <= dp[k]+(sum[i]-sum[k])^2+M;
  所谓j比k优就是DP方程里面的值更小
  对上述方程进行整理很容易得到：
  [(dp[j]+sum[j]*sum[j])-(dp[k]+sum[k]*sum[k])] / 2(sum[j]-sum[k]) <=sum[i].
  注意整理中要考虑下正负，涉及到不等号的方向。
  左边我们发现如果令：yj=dp[j]+sum[j]*sum[j] xj=2*sum[j]
  那么就变成了斜率表达式：（yj-yk）/(xj-xk) <= sum[i];
  而且不等式右边是递增的。
  所以我们可以看出以下两点：我们令g[k,j]=(yj-yk)/(xj-xk)
  第一：如果上面的不等式成立，那就说j比k优，而且随着i的增大上述不等式一定是成立的，也就是对i以后算DP值时，j都比k优。那么k就是可以淘汰的。
  第二：如果 kg[j,i] 那么 j 是可以淘汰的。
  假设 g[j,i] 相反如果 g[j,i]>sum[i] 那么同样有 g[k,j]>sum[i] 那么 k比 j优 那么 j 是可以淘汰的
  所以这样相当于在维护一个下凸的图形，斜率在逐渐增大。
  通过一个队列来维护。

• 代码实现

#include<stdio.h>
#include<string.h>
#include<stack>
#include<algorithm>
using namespace std;
int n,m,a[500010],dp[5000010],sum[500010];
int que[500010];
int getdp(int i,int j)
{
    return dp[j]+(sum[i]-sum[j])*(sum[i]-sum[j])+m;
}
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 2*(sum[j]-sum[k]);
}
int main()
{
    int i,j,k;
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0)
            continue;
        memset(sum,0,sizeof(sum));
        memset(dp,0,sizeof(dp));
        memset(que,0,sizeof(que));
        int l1=0,l2=1;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum[i]=a[i]+sum[i-1];
        }
        for(i=1;i<=n;i++)
        {
            while(l1+1<l2&&getup(que[l1+1],que[l1])<=sum[i]*getdown(que[l1+1],que[l1]))
                l1++;
            dp[i]=getdp(i,que[l1]);
            while(l1+1<l2&&getup(i,que[l2-1])*getdown(que[l2-1],que[l2-2])<=getup(que[l2-1],que[l2-2])*getdown(i,que[l2-1]))
                l2--;
            que[l2++]=i;
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}

• 说明
  

  个人认为比较难理解，看了网上代码写的，暂作为模板。