[HDU 3507]Print Article 斜率优化

题目大意

给出数列C,常数W,
求:
$$ f(i)=min { f(j)+sum(j,i)^2+W } $$
$$ 其中:sum(i,j)=\sum_{k=i}^j C_i $$
的第N项。
N<=1e7

解题报告

一个斜率优化的版题。。
恰巧想到复习斜率优化,在自己的博客上只找到这个:

[BZOJ 1096][ZJOI2007]仓库建设

很版的斜率优化题

什么嘛。。搞半天发现自己没好好写过斜率优化的博客,今天就来补个坑。。

$$ 设k < j < i ,那么从j转移过来优于k的条件如下: $$
$$f(j)+sum(j,i)^2 +W \le f(k)+sum(k,i)^2 +W $$
$$展开移项: f(j)-f(k) \le S_k^2-S_j^2+(S_k-S_j)\times S_i $$
$$其中S_n = \sum_{i=1}^n C_i $$
$$再变换一波:\frac{f(j)+S_j^2-f(k)-S_k^2}{S_k-S_j} \ge 2S_i $$
$$如果我们令y_n=f(n)+S_n^2,x_n=S_n,那么我们发现上面的式子变成了: $$
$$\frac{y_j-y_k}{x_j-x_k} \le -2S_i $$
如果我们把上面(x,y)看成一个二维平面上的点,那么这个[latex]-2S_i[/latex]就是斜率,由于[latex]-2S_i[/latex]是单调递减的(不然就会出现很毒瘤的东西。。),我们在跑动态规划时用单调队列维护一个单调下降的斜率序列就可以O(1)进行转移了。

扯远一点,上面说的’毒瘤’就是动态凸包之类的东西。。
斜率优化基本上就是这个套路了,斜率式一推出来搞定。
还有需要注意的一点就是很多题目里斜率式推出来后等号是可有可无的。。但是大部分情况下,你不打这个等号是会wa的,所以强烈建议能打等号的全部打上等号(毕竟玄学 🙂 )。

代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
const int MAXN = 550000;
int C[MAXN], dp[MAXN];
int sum[MAXN];
int getY(int i) {
    return dp[i] + sum[i]*sum[i];
}
int getX(int i) {
    return sum[i];
}
int seq[MAXN];
int main () {
    int N, M, l, r;
    while(~scanf("%d%d", &N, &M)) {
        for(int i = 1; i<=N; i++)
            scanf("%d", &C[i]), sum[i] = sum[i-1]+C[i];
        l = r = 0; seq[0] = 0;
        for(int i = 1; i<=N; i++) {
            while(l < r && getY(seq[l])-getY(seq[l+1])>=2*sum[i]*(getX(seq[l]) - getX(seq[l+1])))
                l ++;
            dp[i] = dp[seq[l]] + (sum[i] - sum[seq[l]])*(sum[i] - sum[seq[l]]) + M;
            while(l < r && (getY(i)-getY(seq[r]))*(getX(seq[r])-getX(seq[r-1]))
                         <=(getY(seq[r])-getY(seq[r-1]))*(getX(i)-getX(seq[r]))) r--;
            seq[++r] = i;
        }
        printf("%d\n", dp[N]);
    }
}