[动态规划]斜率优化

某著名神犇学习笔记：http://www.cnblogs.com/MashiroSky/p/6009685.html

对于形如$$dp_i=min (dp_j+f(i,j) )$$的方程，无法做到$$ O(1) $$计算 $$ dp_i +f(i,j) $$的最小值，这时就需要斜率优化这个技巧来解决这个问题了。

令 $$ k<j<i $$，当我们更新$$ dp_i $$时，如果有$$dp_j + f(i, j)$$ 比$$dp_k+ f(i, k)$$更优，则有$$dp_j + f(i, j) - (dp_k + f(i, k)<0$$，对于这个不等式如果能够化解成如下形式:

$$\frac{Y(j)-Y(k)}{X(j)-X(k)}<f_i$$

我们就能通过斜率优化这个dp了

Print Article

Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

Problem Description

Zero has an old printer that doesn't work well sometimes. As it is antique, he still like to use it to print articles. But it is too old to work for a long time and it will certainly wear and tear, so Zero use a cost to evaluate this degree.

One day Zero want to print an article which has N words, and each word i has a cost Ci to be printed. Also, Zero know that print k words in one line will cost $$ (\sum ^k _{i=1} Ci)^2 +M $$

M is a const number.

Now Zero want to know the minimum cost in order to arrange the article perfectly.

Input

There are many test cases. For each test case, There are two numbers N and M in the first line (0 ≤ n ≤

500000, 0 ≤ M ≤ 1000). Then, there are N numbers in the next 2 to N + 1 lines. Input are terminated by EOF.

Output

A single number, meaning the mininum cost to print the article.

Sample Input

5 5

5

9

5

7

5

Sample Output

230

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

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

$$ dp[i] = min{dp[j] + M + (sum[i] - sum[j])^2 (0 < j < i)} $$

令$$k<j<i$$，当有:

$$ dp[j] + M + (sum[i] - sum[j])^2 - (dp[k] + M + (sum[i] - sum[k])^2) < 0 $$

从j转移到i, 比从k转移到i更优，变换此不等式可得:

$$ \frac{(dp[j]+ sum[j]^2) - (dp[k] + sum[k]^2)}{sum[j] - sum[k]} < 2sum[i] $$

令$$ Y(i) = dp[i] + sum[i]^2 $$,$$ X(i) = sum[i] $$, $$ f[i]=2sum[i]$$则将此不等式化解为上述形式.

可以发现，若满足$$ \frac {Y(j) - Y(k)} { X(i) - X(j)} < f(i) $$则j转移到i，比k转移到i更优，如果我们把(X(j), Y(j)), (X(k), Y(k))当成平面上的两个点Pj, Pk，这个不等式的含义即为若$$ \overrightarrow{P_jP_k} $$的斜率＜f(i)则，从j转移更优。

令grad(i, j)表示$$ \overrightarrow{P_iP_j} $$的斜率，现在我们假设grad(i,j) <grad(j, k)，若grad(i, j) < f(I),则i比j更优，若grad(i, j) > f(I), 则grad(j, k) > f(I),那么从k转移比从j转移更优，当grad(i, j) < grad(j, k)的时候，无论如何j转移到i都不会是最优。而这种情况恰好对应下图

所以这种情况时，我们可以直接把j点删除，最后能够转移的点集只会存在这种图形，

所以最后我们维护一个上凸集即可。

但是此时我们还是没有解决最终问题，如何才能找到转移到i点的最优的点呢。可以发现最后的点集一定是一个凸集，也就是斜率单调！！这样对于k < j, grad(j,k) < f(i),时更优，从图形特点我们可以发现如果j比k优，那么j点比所有比k小的点都优，所以对于每一个f(i),我们维护一个所有比i点小的凸集，二分查找斜率比f(i)小的编号最大的点，就是最优的转移点。

#include<iostream>
#include<string>
using namespace std;

int dp[500005];
int q[500005];
int sum[500005];
int head,tail,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)  //yj-yk的部分
{
    return dp[j]+sum[j]*sum[j]-(dp[k]+sum[k]*sum[k]);
}

int getDOWN(int j,int k) //xj-xk的部分
{
    return 2*(sum[j]-sum[k]);
}

int main()
{
    int i;
    while(scanf("%d%d",&n,&m)==2)
    {
        for(i=1;i<=n;i++)
            scanf("%d",&sum[i]);
        sum[0]=dp[0]=0;
        for(i=1;i<=n;i++)
            sum[i]+=sum[i-1];
        head=tail=0;
        q[tail++]=0;
        for(i=1;i<=n;i++)
        {
            while(head+1<tail && getUP(q[head+1],q[head])<=sum[i]*getDOWN(q[head+1],q[head]))
                head++;
            dp[i]=getDP(i,q[head]);
            while(head+1<tail && getUP(i,q[tail-1])*getDOWN(q[tail-1],q[tail-2])<=getUP(q[tail-1],q[tail-2])*getDOWN(i,q[tail-1]))
                tail--;
            q[tail++]=i;
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}

[动态规划]斜率优化的DP