题目链接

其实这一篇文章是为了补上一篇文章的坑…斜率优化是决策单调性优化的一中特殊形式。

<h2>题目描述</h2>

你可以连续的输出一些单词，定义每个单词的度为 $ a[i] $ ,则输出 $ i $ 到 $ j $ 的词的代价是 $(\Sigma^k _{i=1} a[i])^2 + M$。单词不能打乱顺序输出。

其中 $ N \leq 500000,M \leq 1000 $

<h2>解题报告</h2>

这是一道基本的斜率优化的题目。

动态规划的式子我们都很好推，设 $ f_i $ 表示输出前 $i$ 个单词的最小代价，有转移方程

$$ f_i = min&#123;f_j + (S_j-S_i)^2 + M&#125; $$

其中 $1 \leq j &lt; i$，$ S$ 表示 $a$ 的前缀和。

但这个朴素的 dp 是 $O(n^2)$，会超时。我们要想办法 $O(1)$ 找出 $ min( f_j + (S_j-S_i)^2 + M ) $。

于是我们不妨设在这个转移求 $f_i$ 的过程中，从 $j$ 转移要比从 $k$ 转移要更优 $(j &lt; k)$ 。如此可以得到：

$ f_j + (S_j - S_i)^2 + M &lt; f_k + (S_k-S_i) + M \tag 1$

进行一系列的小学数学化简，得到

（为了简便这里的 $S_i$ 表示 $1$ 到 $i-1$ 的和）

$$ \frac{f_j-f_k+S_j^2-S_k^2}{S_j-S_k} &lt; 2S_{i+1} \tag2$$

我们不妨设 $ F_i = f_i + S_i\ ^2 $，那么式子可以表示为：

$$ \frac{F_j - F_k}{S_j - S_k} &lt; 2S_{i+1}\tag3$$

即当且仅当 $ (j &lt; k) $ 且 $$ \frac{F_j - F_k}{S_j - S_k} &lt; 2S_{i+1} $$ 成立的时候，从 $j$ 转移才更优。

然后我们发现这个式子...很像斜率。我们对于每一个确定的状态对应到空间中每一个点 $ (S_i,F_i) $。

进行转移的时候，考虑在一条直线上的两个点，他们的斜率关系能直接反应是否从这里转移。

所以说我们就维护一个下凸壳，每次更新出状态的时候加入这个点并维护凸壳，但还是不能 $O(1)​$ 求。

其实最后我们发现这个函数是单调的，可以用单调队列维护，达到了 $O(1) $ 找出转移状态的目的。

时间复杂度最后为 $O(n)$

<h2>代码</h2>

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define R register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(R int i = a;i <= b;++i)
#define RFOR(i,a,b) for(R int i = a;i >= b;--i)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 500000 + 5;
int N,M;
int a[MAXN],f[MAXN],sum[MAXN];
int q[MAXN],head,tail;

// f[i] = min{f[j] + (sum[i]-sum[j-1])^2 + M}
//
#define Y(i) (f[i] + sum[i] * sum[i])
#define X(i) (sum[i])

inline bool headpop(int a,int b,int x){
    return Y(b) - Y(a) <= 2  sum[x]  (X(b) - X(a));
}

inline bool tailpop(int a,int b,int c){
    return (Y(b) - Y(a))  (X(c) - X(b)) >= (Y(c) - Y(b))  (X(b) - X(a));
}

inline int calc(int i,int j){
    return f[j] + (sum[i]-sum[j])*(sum[i]-sum[j]) + M;
}

int main(){
    while(~scanf("%d%d",&N,&M)){
        FOR(i,1,N) scanf("%d",a + i);
        f[0] = sum[0] = 0;
        FOR(i,1,N) sum[i] = sum[i-1] + a[i];
        q[head = tail = 0] = 0;
        FOR(i,1,N){
            while(head < tail && headpop(q[head],q[head+1],i)) head++;
            f[i] = calc(i,q[head]);
            while(head < tail && tailpop(q[tail-1],q[tail],i)) tail--;
            q[++tail] = i;
        }
        printf("%dn",f[N]);
    }
    return 0;
}