单调队列

在这之前去学了下单调队列优化，大概就是DP的时候要从前面某个地方转移过来，DP方程里除了新增的量和前面没什么关系的时候就可以用单调队列。 $f[i] = min \\{f[j]+g(i) \\}$
其中$g(i)$函数和$j$没关系。其实本来维护一波$f$前缀里的最优解就可以的，如果有一些下标上的限制（诸如相差不超过$k$），就要用单调队列了。
不难证明时间复杂度从$O(N^2)$优化到了$O(N)$。
~~随便放个屁~~

斜率优化

上面问题的升级版。

$f[i] = min \\{f[j]+g(i, j) \\}$

也就是说$g$和$i、j$都有关系。

直接用两个水题说

HDU3507

题目大意

已知数组$C$，要求将其分成若干段，每一段的代价是$\sum{C_i}+M$，其中$M$是常数。

Solution

先写下暴力
记$s$是$c$的前缀和。

$f[i] = min \\{ f[j-1] + (s[i]-s[j-1])^2 + M\\}$

假设决策点$k$比$j$更优。
不妨设$k \lt j$那么应该满足条件：

$f[k-1] + (s[i]-s[k-1])^2 + M \lt f[j-1] + (s[i]-s[j-1])^2 + M$

简单变换一下，得到

$f[k-1] +s[i]^2 + s[k-1]^2 - 2 \times s[i] \times s[k-1] \lt f[j-1] + s[i]^2 + s[j-1]^2 - 2 \times s[i] \times s[j-1]$

令$y[i] = f[i-1] +s[i-1]^2$,$x[i] = s[i-1]$，合并、换元可得

$y[k] - y[j] \lt 2 \times s[i] \times (x[k] - x[j])$

由于$s$递增，移项可得

$\frac{y[k] - y[j]}{x[k] - x[j]} \lt 2 \times s[i]$

不难发现式子左边就是斜率的形式。

视情况（即最大化还是最小化）维护上凸壳或者下凸壳。正确性的证明，运用反证法拉出最后的三个点，讨论最后两个点之间的斜率和$2 \times s[i]$之间的大小关系即可。

#include <bits/stdc++.h>
using namespace std ;
const int maxn = 5e5+5 ;
int n, m, s[maxn], f[maxn] ;
int Q[maxn*2], head, tail ;
int H ( int x ) { return f[x-1] + s[x-1]*s[x-1] ; }
void DP() {
    memset ( Q, 0, sizeof Q ) ;
    head = tail = 1 ;
    Q[head] = 1 ;
    f[1] = s[1]*s[1]+m ;
    for ( int i = 2 ; i <= n ; i ++ ) {
        while (head < tail) {
            if ((H(i)-H(Q[tail]))*(s[Q[tail]-1]-s[Q[tail-1]-1]) <= (H(Q[tail])-H(Q[tail-1]))*(s[i-1]-s[Q[tail]-1]))
                --tail ;
            else break ;
        }
        Q[++tail] = i ;
        while (head < tail) {
            if (H(Q[head+1])-H(Q[head]) < 2*(s[Q[head+1]-1]-s[Q[head]-1])*s[i])
                ++head ;
            else break ;
        }
        f[i] = f[Q[head]-1] + (s[i]-s[Q[head]-1])*(s[i]-s[Q[head]-1])+m ;
    }
    printf ( "%d\n", f[n] ) ;
}
int main() {
    while (scanf ( "%d%d", &n, &m ) != EOF) {
        for ( int i = 1 ; i <= n ; i ++ ) {
            scanf ( "%d", s+i ) ;
            s[i] += s[i - 1] ;
        }
        DP() ;
    }
    return 0 ;
}

还两道题懒得写详细过程了，反正都是一样的。

[HNOI2008]玩具装箱TOY

#include <bits/stdc++.h>
#define LL long long
using namespace std ;
void Read ( LL &x, char c = getchar() ) {
    for ( x = 0 ; !isdigit(c) ; c = getchar() ) ;
    for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
}
int o[50] ;
void print ( LL x, int len = 0 ) {
    if (x == 0) {
        putchar('0') ;
        return ;
    }
    for ( ; x ; x /= 10 ) o[++len] = x%10 ;
    while (len) putchar(o[len--]+'0') ;
}
const LL maxn = 50005 ;
LL n, m, s[maxn], a[maxn] ;
LL f[maxn], Q[maxn], head, tail ;
LL H ( LL x ) { return f[x-1] + a[x-1]*a[x-1] ; }
void solve() {
    head = tail = 1 ;
    f[1] = (s[1]-m+1)*(s[1]-m+1) ;
    for ( int i = 2 ; i <= n ; i ++ ) {
        while (head < tail) {
            if ((H(i) - H(Q[tail]))*(a[Q[tail]-1]-a[Q[tail-1]-1]) < (H(Q[tail])-H(Q[tail-1]))*(a[i-1]-a[Q[tail]-1]))
                -- tail ;
            else break ;
        }
        Q[++tail] = i ;
        while (head < tail) {
            if (H(Q[head+1])-H(Q[head])<2*(a[i]-m)*(a[Q[head+1]-1]-a[Q[head]-1]))
                ++ head ;
            else break ;
        }
        f[i] = f[Q[head]-1] + (a[i]-a[Q[head]-1]-m)*(a[i]-a[Q[head]-1]-m) ;
    }
    print(f[n]) ;
    putchar('\n') ;
}
int main() {
    Read(n) ; Read(m) ;
    for ( int i = 1 ; i <= n ; i ++ ) {
        Read(s[i]) ;
        s[i] += s[i - 1] ;
        a[i] = s[i]+i ;
    }
    ++ m ;
    solve() ;
    return 0 ;
}

[APIO2010]特别行动队

#include <bits/stdc++.h>
#define LL long long
using namespace std ;
void Read ( LL &x, char c = getchar(), bool fg = 0 ) {
    for ( x = 0 ; !isdigit(c) ; c = getchar() ) if (c == '-') fg = 1 ;
    for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
    if (fg) x = -x ;
}
const LL maxn = 1e6+5 ;
LL n, m, s[maxn], f[maxn], Q[maxn], head, tail, a, b, c ;
LL H ( LL x ) { return f[x-1] + a*s[x-1]*s[x-1] - b*s[x-1] ; }
void solve() {
    head = tail = 1 ;
    Q[head] = 1 ;
    f[1] = a*s[1]*s[1] + b*s[1] + c ;
    for ( int i = 2 ; i <= n ; i ++ ) {
        while (head < tail) {
            if ((H(i)-H(Q[tail]))*(s[Q[tail]-1]-s[Q[tail-1]-1])>(H(Q[tail])-H(Q[tail-1]))*(s[i-1]-s[Q[tail]-1]))
                --tail ;
            else break ;
        }
        Q[++tail] = i ;
        while (head < tail) {
            if (H(Q[head+1])-H(Q[head])>2*a*s[i]*(s[Q[head+1]-1]-s[Q[head]-1])) ++ head ;
            else break ;
        }
        f[i] = f[Q[head]-1]+a*(s[i]-s[Q[head]-1])*(s[i]-s[Q[head]-1])+b*(s[i]-s[Q[head]-1])+c ;
    }
    printf ( "%lld\n", f[n] ) ;
}
int main() {
    Read(n) ;
    Read(a) ; Read(b) ; Read(c) ;
    for ( int i = 1 ; i <= n ; i ++ ) {
        Read(s[i]) ;
        s[i] += s[i - 1] ;
    }
    solve() ;
    return 0 ;
}

据说只刷模板题会变蠢？