题目描述

难度分:$2000$

输入$n(1 \leq n \leq 10^5)$，$s(0 \leq n \leq 10^9)$，$L(1 \leq n \leq 10^5)$和长为$n$的数组$a(-10^9 \leq a[i] \leq 10^9)$。

你需要把$a$分割成若干段（连续子数组），满足：

1. 每段长度至少为$L$。
2. 每段的最大值减最小值$\leq s$。

输出至少要把$a$分成多少段。

如果无法做到，输出$-1$。

输入样例$1$

7 2 2
1 3 1 2 4 1 2

输出样例$1$

3

输入样例$2$

7 2 2
1 100 1 100 1 100 1

输出样例$2$

-1

算法

单调队列优化DP

需要先进行一个预处理，便于快速查询区间最值，从而计算区间的极差。由于数组$a$中的元素都是不变的，因此可以直接用倍增来进行预处理。

倍增预处理

通过倍增算法预处理两个数组$f_{mx}$和$f_{mn}$，其中$f_{mx}[i][j]$和$f_{mn}[i][j]$分别表示的是子数组$[i,i+2^j)$内的最大值和最小值。实现一个查询函数$query(l,r)$，用于查询子数组$[l,r]$上的极差，利用倍增预处理出来的$f_{mx}$和$f_{mn}$数组，也可以在$O(log_2n)$的时间复杂度下求出来。

这部分的原理还是有点复杂的，但是个比较固定的套路，可以当模板使用，本质上是个区间DP。

动态规划

状态定义

$dp[i]$表示将子数组$[1,i]$划分为极差不超过$s$，且长度不小于$l$的最小段数。

状态转移

令$dp[0]=0$，当最后一段以$a[i]$结尾时，上一段的右端点$j$应该满足$j \in [0,i-l]$。此时状态转移方程就应该为：

$dp[i]=min_{j \in [0,i-l]}dp[j] + 1$

直接遍历所有符合题意的$j$的话状态转移就是$O(n)$的，整个算法的时间复杂度就是$O(n^2)$，肯定会超时。注意到这是求区间最值，可以借助$query$函数利用单调队列来优化状态转移的时间复杂度。

准备一个队列$q$存储$j \in [0,i-l]$，保证队头到队尾的$dp[j]$是单调递增的。当遍历到$a[i]$时，如果$dp[q.back()] \geq dp[i-l]$就弹出队尾，然后把$j$尾插进队列，然后再检查$[q.front()+1,i]$的极差是否不超过$s$（为了保证最后一段$[j+1,i]$的极差不超过$s$），如果超过$s$了就要弹出队头。这样一来状态转移方程就是：

$dp[i]=dp[q.front()]+1$

注意队列为空的边界情况即可。

复杂度分析

时间复杂度

倍增预处理出$f_{mx}$和$f_{mn}$数组的时间复杂度为$O(nlog_2n)$，单调队列优化DP理论上是$O(n)$的，但是在判断队头元素是否要弹出时，需要调用$query$函数检查子数组$[q.front()+1,i]$的极差是否不超过$s$，所以状态转移并不是$O(1)$的，而是$O(log_2n)$。综上，整体算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

空间瓶颈主要在于$f_{mx}$和$f_{mn}$两个数组，它们的规模都是$O(nlog_2n)$，因此算法的额外空间复杂度为$O(nlog_2n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <cmath>

using namespace std;

const int N = 100010, M = 21, INF = 0x3f3f3f3f;
int n, s, l, a[N], fmn[N][M], fmx[N][M], dp[N];

// 倍增
void init() {
    for(int j = 0; j < M; j++) {
        for(int i = 1; i + (1 << j) - 1 <= n; i++) {
            if(!j) {
                fmn[i][j] = fmx[i][j] = a[i];
            }else {
                fmn[i][j] = min(fmn[i][j - 1], fmn[i + (1<<j - 1)][j - 1]);
                fmx[i][j] = max(fmx[i][j - 1], fmx[i + (1<<j - 1)][j - 1]);
            }
        }
    }
}

int query(int left, int right) {
    int len = right - left + 1;
    int k = log(len) / log(2);
    return max(fmx[left][k], fmx[right - (1<<k) + 1][k]) - min(fmn[left][k], fmn[right - (1<<k) + 1][k]);
}

int main() {
    scanf("%d%d%d", &n, &s, &l);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    init();
    memset(dp, 0x3f, sizeof(dp));
    deque<int> q;
    dp[0] = 0;
    for(int i = l; i <= n; i++) {
        int j = i - l;
        while(!q.empty() && j >= 0 && dp[q.back()] >= dp[j]) {
            q.pop_back();
        }
        if(j >= 0 && query(j + 1, i) <= s) {
            q.push_back(j);
        }
        while(!q.empty() && query(q.front() + 1, i) > s) {
            // [q.front() + 1, i]的极差不超过s，才能把这一段分出来
            q.pop_front();
        }
        if(!q.empty()) {
            dp[i] = min(dp[i], dp[q.front()] + 1);
        }
    }
    printf("%d\n", dp[n] == INF? -1: dp[n]);
    return 0;
}