题解：CF487B Strip

Carey_chen · 2025-02-08 15:36:07 · 题解

这是一种双指针+ ST 表做法。

首先可以想到一个简单的 dp ，定义 dp_i 表示 [1, i] 至少需要分成的段数。

可以得到：

这个式子可以 O(n^2) 转移：在枚举 j 时可顺便更新区间的的最大值和最小值。

还可以进一步优化，由于越往后分得的段数越多， dp 数组除去无解部分一定单调不降。即： j 越小，它越容易成为那个最小值。所以要对每一个 dp_{i} 找到一个最小的 j 满足题目要求。

在同一序列中，[j, i] 的最大值和最小值之差一定大于等于 [j+1, i] 的，所以在 i 递增时 j 一定不降，可以使用双指针维护 j，再加上 ST 表求最大值和最小值之差。

#include <bits/stdc++.h>

using namespace std;

int a[100010], dp[100010];
int Max[100010][30], Min[100010][30], nxt[100010][30];

int QMax(int l, int r) {...} // 求区间最大值
int QMin(int l, int r) {...} // 求区间最小值

int main()
{
    int n, s, l;
    scanf("%d %d %d", &n, &s, &l);

    memset(Min, 0x3f, sizeof(Min));
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        Max[i][0] = a[i];
        Min[i][0] = a[i];
        nxt[i][0] = i + 1;
    }

    for(int j = 1; j <= 20; j++)
    {
        for(int i = 1; i <= n; i++)
        {
            nxt[i][j] = nxt[nxt[i][j-1]][j-1];
            Max[i][j] = max(Max[i][j-1], Max[nxt[i][j-1]][j-1]);
            Min[i][j] = min(Min[i][j-1], Min[nxt[i][j-1]][j-1]);
        }
    }

    dp[0] = 0;

    for(int i = 1, j = 0; i <= n; i++)
    {
        while(j + 1 < i && (QMax(j + 1, i) - QMin(j + 1, i) > s || dp[j] == 1e9))
        {
            j++;
        }
        if(i - j >= l)
        {
            dp[i] = dp[j] + 1;
        }
        else
        {
            dp[i] = 1e9;
        }
    }

    printf("%d", dp[n] == 1e9 ? -1 : dp[n]);

    return 0;
}