题目链接 Strip
题意 把一个数列分成连续的$k$段，要求满足每一段内的元素最大值和最小值的差值不超过$s$，
同时每一段内的元素个数要大于等于$l$，
求$k$的最小值。
考虑$DP$
设$dp[i]$为前$i$个数字能划分成区间个数的最小值。
则$dp[i] = min(dp[j] + 1)$
于是下一步就是求符合条件的j的范围。
构建$ST$表，支持区间查询最大值和最小值。
对于每一个位置$x$，我们知道$max(a[i]...a[x]) - min(a[i]...a[x])$肯定是随着i的减小非递减的。$(i <= x)$
于是我们就可以通过二分求出符合条件的$max(a[i]...a[x]) - min(a[i]...a[x])$的最小值，记为$c[x]$
当不存在可以转移到$dp[x]$的$dp[i]$时，$c[x]$为$-1$。
$n <= 100000$，考虑用线段树优化。
单点更新，区间查询最小值。
时间复杂度$O(nlogn)$
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
#define lson i << 1, L, mid
#define rson i << 1 | 1, mid + 1, R
typedef long long LL;
const int N = 1e5 + 10;
const int A = 18;
int f[N][A], g[N][A];
int a[N], lg[N], c[N], dp[N];
int n, s, l;
int L, R;
int t[N << 2];
void ST(){
rep(i, 1, n) f[i][0] = a[i];
rep(j, 1, 17) rep(i, 1, n)
if ((i + (1 << j) - 1) <= n) f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
rep(i, 1, n) g[i][0] = a[i];
rep(j, 1, 17) rep(i, 1, n)
if ((i + (1 << j) - 1) <= n) g[i][j] = max(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]);
}
inline int solvemin(int l, int r){
int k = lg[r - l + 1];
return min(f[l][k], f[r - (1 << k) + 1][k]);
}
inline int solvemax(int l, int r){
int k = lg[r - l + 1];
return max(g[l][k], g[r - (1 << k) + 1][k]);
}
inline void pushup(int i){ t[i] = min(t[i << 1], t[i << 1 | 1]);}
void build(int i, int L, int R){
if (L == R){ t[i] = 1 << 30; return;}
int mid = (L + R) >> 1;
build(lson);
build(rson);
pushup(i);
}
void update(int i, int L, int R, int x, int val){
if (L == R && L == x){ t[i] = min(t[i], val); return;}
int mid = (L + R) >> 1;
if (x <= mid) update(lson, x, val);
else update(rson, x, val);
pushup(i);
}
int query(int i, int L, int R, int l, int r){
if (L == l && R == r) return t[i];
int mid = (L + R) >> 1;
if (r <= mid) return query(lson, l, r);
else if (l > mid) return query(rson, l, r);
else return min(query(lson, l, mid), query(rson, mid + 1, r));
}
int main(){
rep(i, 1, 1e5 + 1) lg[i] = (int)log2((double)(i));
scanf("%d%d%d", &n, &s, &l);
rep(i, 1, n) scanf("%d", a + i);
ST();
if (l <= 1) c[1] = 1; else c[1] = -1;
rep(i, 2, n){
L = 1, R = i - l + 1;
if (R < 1){ c[i] = -1; continue; }
if (solvemax(R, i) - solvemin(R, i) > s){ c[i] = -1; continue;}
while (L + 1 < R){
int mid = (L + R) >> 1;
if (solvemax(mid, i) - solvemin(mid, i) <= s) R = mid;
else L = mid + 1;
}
if (solvemax(L, i) - solvemin(L, i) <= s) c[i] = L;
else c[i] = R;
}
dp[0] = 0;
rep(i, 1, n) dp[i] = 1 << 30;
build(1, 1, n + 1);
update(1, 1, n + 1, 1, 0);
rep(i, 1, n){
if (c[i] == -1) continue;
int now = query(1, 1, n + 1, c[i], i - l + 1);
dp[i] = min(dp[i], now + 1);
update(1, 1, n + 1, i + 1, dp[i]);
}
if (dp[n] < (1 << 30)) printf("%d
", dp[n]);
else puts("-1");
return 0;
}
上面这个方法很容易想，但是写起来略有难度。
其实有一种更好的方法。
用单调队列来优化。
对于当前的这个$x$，向后扫描，扫到y的时候如果发现区间$[x, y]$不符合题意了。
那么其实这个时候$x$这个位置已经没用了。
因为如果$[x,y]$不符合题意，那么$[x, y + 1]$肯定是不符合题意的。
于是我们可以用单调队列优化，用集合来维护最大值和最小值。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
const int N = 1e5 + 10;
int n, s, l, now;
int a[N], f[N];
multiset <int> st, v;
int main(){
scanf("%d%d%d", &n, &s, &l);
rep(i, 1, n) scanf("%d", a + i);
now = 1;
f[0] = 0;
rep(i, 1, n){
f[i] = 1 << 30;
st.insert(a[i]);
if (i - now + 1 >= l) v.insert(f[i - l]);
while (*st.rbegin() - *st.begin() > s){
st.erase(st.find(a[now]));
auto it = v.find(f[now - 1]);
if (it != v.end()) v.erase(it);
// if (i - now + 1 >= l) v.erase(v.find(f[now - 1]));
++now;
}
if (!v.empty()) f[i] = *v.begin() + 1;
}
printf("%d
", f[n] >= (1 << 30) ? -1 : f[n]);
return 0;
}